I am writing Pacman, for the pursuit algorithm I took the wave algorithm, but how not to twist, it is heavy. When updating the coordinates of the peckman, the path of the ghost to him is updated, and here the search for the shortest path makes itself felt. What are more efficient algorithms on matrices?

Here is the code for finding the path:

void Enemy::getPathToTarget() { pathToPacman.clear (); const Position * playerPosition = Player::playerPosition (); Field = Maze::getField (); int height = Field.size(); int width = Field[0].size(); int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int d, x, y, k; bool stop; Field[playerPosition->x][playerPosition->y] = 1; if (Field[position->x][position->y] == 0 || Field[playerPosition->x][playerPosition->y] == 0) return; d = 6; Field[position->x][position->y] = 6; do { stop = true; for ( y = 0; y < height; ++y ) for ( x = 0; x < width;++x ) if ( Field[y][x] == d ) { for ( k = 0; k < 4; ++k ) { int iy=y + dy[k]; int ix = x + dx[k]; if ( iy >= 0 && iy < height && ix >= 0 && ix < width && ((Field[iy][ix] == 1) || (Field[iy][ix] == 2) || (Field[iy][ix] == 3))) { stop = false; Field[iy][ix] = d + 1; } } } ++d; } while ( !stop && (Field[playerPosition->x][playerPosition->y] == 1 || (Field[playerPosition->x][playerPosition->y] == 2) || Field[playerPosition->x][playerPosition->y] == 3)); if (Field[playerPosition->x][playerPosition->y] == 1) return; d = Field[playerPosition->x][playerPosition-> y = playerPosition->x; x = playerPosition->y; int val = 0; while ( d > 6 ) { pathToPacman.push (Position(y, x)); d--; for (k = 0; k < 4; ++k) { int iy=y + dy[k], ix = x + dx[k]; if ( iy >= 0 && iy < height && ix >= 0 && ix < width && Field[iy][ix] == d) { x = x + dx[k]; y = y + dy[k]; break; } } } timer.start (10000); }
  • 3
    It is necessary to write a very crooked search for the shortest path on the lattice (on the matrix) so that it makes itself felt. For the same length of edges, its complexity is O(n) , where n is the number of vertices of the lattice graph. - Zealint 5:09
  • It turns out that he scatters the waves for a very long time, until he reaches the given coordinates ... - Max
  • one
    @Max, even with a table size of 1000 * 1000, it is really possible to do 100 calculations per second on a weak iron. - pavel
  • @pavel Torvalds said: “Chatter is worth nothing, show us the code.” The code is here. If you say that everything should be so gazing, then please indicate where I was wrong. - Max
  • @Max I can give an algorithm that works so fast. If you wrote more slowly, then this is exactly the mistake of your algorithm. And the most important place is do { for ( y = 0; y < height; ++y ) for ( x = 0; x < width;++x ) Nothing that is already a potential complexity instead of O(N*M) O(N*N*M*M) did not read further. This is not a wave circuit and has nothing to do with it. I tried to find a minute 2 in this code for a очередь or something (an array, a list, a vector) like it, failed. - pavel

1 answer 1

You have the following conditions:

  1. Labyrinth with corridors 1 cage wide

  2. 1 - 3 directions of movement, because the ghost can not turn on the previous cell.

  3. Pacman position

  4. Phantom Position

Hence, the simplest algorithm for sequential cell search with a sample of the minimum distance.

If you want to implement the classic pursuit algorithm, then note that each ghost has its own pattern of behavior and only the Red Ghost is guided exactly by the position of Pacman. If English is not a problem, I strongly recommend that you familiarize yourself with PacMan Dossier, where the details of the game are described in detail. http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php?print=1

Here is my example of implementing C # as a junior, but I think it will not be difficult to figure it out. Naturally, the code can be simplified in one cycle into 4 directions, but here I left it in detail for clarity:

Update: I forgot to mention that there is no need to search all the way to Pakman, you need to search only for the most preferred cell for the next step. This code is just for selecting the next step.

 protected void GetMinNextPosition() { int ix = Mathf.FloorToInt(_myTrans.position.x); int iy = Mathf.FloorToInt(_myTrans.position.y); float dist = float.MaxValue; Direction _potencialDir = Direction.None; if (!GameManager.Instance.Map[ix - 1, iy].IsObstacle && _oppositeDirection != Direction.Left) { float newDist = Vector3.Distance(new Vector3(ix - 1, iy), _target); if (newDist < dist) { dist = newDist; _potencialDir = Direction.Left; } } if (!GameManager.Instance.Map[ix + 1, iy].IsObstacle && _oppositeDirection != Direction.Right) { float newDist = Vector3.Distance(new Vector3(ix + 1, iy), _target); if (newDist < dist) { dist = newDist; _potencialDir = Direction.Right; } } if (!GameManager.Instance.Map[ix, iy - 1].IsObstacle && _oppositeDirection != Direction.Down) { float newDist = Vector3.Distance(new Vector3(ix, iy - 1), _target); if (newDist < dist) { dist = newDist; _potencialDir = Direction.Down; } } if (!GameManager.Instance.Map[ix, iy + 1].IsObstacle && _oppositeDirection != Direction.Up) { float newDist = Vector3.Distance(new Vector3(ix, iy + 1), _target); if (newDist < dist) { dist = newDist; _potencialDir = Direction.Up; } } SetDirection(_potencialDir, ix, iy); }