-1

This is a question related to another question where you helped me a lot.

My new question is, is there a way to print the found path from the source cell to the target cell? Or, is there a way to get only the first move from pred without iterating all of it?

In the (Very helpful) answer I received in the other question I was suggested to get the path from target to source, that is very useful but in order to improve my code I'd the path from source to target.

My problem is that I'm trying to write a rogue-like game and I have to tell a monster which will be his next move and I think iterating all of the pred array in order to get a single move it's a waste of resources.

Thank you in advance for the help.

Aster
  • 143
  • 2
  • 11

1 Answers1

0

Now that you have a path mapped out, look for the next * beside the monster:

if (G->nodes[T.row + A][T.col + B] == '*') {
    //kept for my sanity: pred[G->T.row*G->col + G->T.col]

    doMove(); //don't forget to change the '*' into 'T', then the old spot to ' '
}

To do a move up, check A = -1; B = 0. To do a move down, check offsetA = 1; offsetB = 0. Right: A = 0; B = -1, Left: A = 0; B = 1.

Because your maps are very simple and don't branch very far, I recommend you choose a faster algorithm. BFS tends to search for the nearest paths and isn't very efficient for long paths. Djikstra's is a better implementation of BFS allowing a cost to be assigned to edges. A* is the best search to use in games because it is Djikstra's algorithm that speeds up (converges faster) when it has no obstacles by exploiting knowledge of its goal.

Aaron3468
  • 1,734
  • 16
  • 29