1
$\begingroup$

I have a table that looks like this

enter image description here

In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user.

In any moment the player character might move to any cell of the table. But NPC has a particular goal cell that they should reach while moving. For example, blue NPC needs to read blue cell.

enter image description here

Other NPC are also moving. My goal is to write an algorithm that would allow NPC to reach the cell using the shortest path. As far as I understand it is a typical shortest path problem.

My question is - is there some algorithm that particularly optimized to handle such workflows, or any algorithms will suffice - just with recalculating the path after each move?

$\endgroup$
1
$\begingroup$

There are many; you can find a list here. The most applicable is probably D*-lite.

However, there are not many off-the-shelf implementations for it, so the vast majority of games just recalculate the best path using A*. There are many visual and technical tricks for recalculating as infrequently as possible without negatively affecting the game, but that's more of a question for gamedev.stackexchange.com.

For NPCs in particular, you may also want to look into pathfinding with many units at once. Some typical search-terms for this are "swarm pathfinding", "boids", "flocking behaviors", and "collision avoidance pathfinding"

$\endgroup$
  • $\begingroup$ looking at D* (and LPA*) it seems they both maintain successors and predecessor vertices. but for undirected graph - what they might be? all vertices around? $\endgroup$ – lapots Jun 16 at 15:44
  • 1
    $\begingroup$ @lapots: Yes. Every directed graph algorithm also works on undirected graphs, because you can turn an undirected graph into a directed graph by replacing every edge with two edges, one in each direction (with both having the same weight) $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 16 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.