Linked Questions

33
votes
12answers
7k views

How can I make A* finish faster when the destination is impassable?

I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an ...
30
votes
2answers
4k views

Is A* efficient even when the obstacles are moving?

I'm just starting to learn about path-finding and have been looking into the A* algorithm and my main concern is that it all of the examples I have seen show static obstacles that it computes around. ...
11
votes
2answers
3k views

Tweaking AStar to find closest location to unreachable destination

I've implemented AStar in Java and it works ok for an area with obstacles where the chosen destination is reachable. However, when the destination is unreachable, the calculated "path" is in no way ...
7
votes
2answers
1k views

Low CPU/Memory/Memory-bandwith Pathfinding (maybe like in Warcraft 1)

Dijkstra and A* are all nice and popular but what kind of algorithm was used in Warcraft 1 for pathfinding? I remember that the enemy could get trapped in bowl-like caverns which means there were (...
8
votes
1answer
631 views

How can City-sim simulate hundreds of characters?

My games usually start lagging quite easily when there are a couple hundred of boxes representing possible characters. While games like SimCity or even Anno have hundreds of characters. I realized ...
4
votes
1answer
1k views

How to determine that nodes in Grid Graph are unreachable before applying pathfinding?

I would like to determine accessibility of nodes before applying pathfinding algorithm to Grid Graph. I have a surface with nodes overlayed on it and I would like to somehow determine that nodes ...
4
votes
1answer
940 views

Path finding in games

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;) So, i've done a little bit of searching ...
1
vote
1answer
121 views

What technique can I use to animate interaction between tiny objects in a sim game?

In simulation games like Sim City and Factorio, there are numerous interaction between tiny objects that needs to be animated. e.g. random people walking on the sidewalk, then waits for a bus, then ...
4
votes
4answers
187 views

2D Top Down: Can't follow the path accurately

In my game, there are many agents. Agents request a path, then after attaining a path to "goal" they follow the path. However player and many other things in the world can impact their position by ...
1
vote
2answers
67 views

How can I improve the performance of my A* pathfinding code?

I'm currently working on implementing A* pathfinding into a little project of mine. My ideal goal is that my game should be able to handle about 1000+ objects without any noticable impact on ...
1
vote
1answer
53 views

Determining and Re-Considering Trapped Targets when Path-finding

I have a game that has multiple path-finding agents (A*) with a grid based map. The player can change the map by constructing walls, floors etc. and the agents will move to construct what the player ...
2
votes
0answers
45 views

How can I implement caching into my Rectangular Symmetry Reduction pathfinding algorithm?

I have a working implementation of Rectangular Symmetry Reduction (see here and here for more information on RSR). I'm interested in further improving performance over raw A* by implementing caching ...