Linked Questions

34 votes
12 answers
9k 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 ...
user2499946's user avatar
30 votes
2 answers
5k 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. ...
Ethan The Brave's user avatar
13 votes
2 answers
5k 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 ...
Shivan Dragon's user avatar
8 votes
2 answers
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 (...
Valmond's user avatar
  • 2,454
7 votes
1 answer
1k 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 ...
MisteriosM's user avatar
4 votes
1 answer
2k 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 ...
Patryk's user avatar
  • 397
4 votes
1 answer
1k 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 ...
Darvex's user avatar
  • 151
2 votes
2 answers
810 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 ...
olawrdhalpme's user avatar
5 votes
4 answers
226 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 ...
Blue Bug's user avatar
  • 1,112
1 vote
1 answer
284 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 ...
Jake's user avatar
  • 547
2 votes
0 answers
192 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 ...
Raven Dreamer's user avatar
1 vote
1 answer
86 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 ...
Alex's user avatar
  • 241