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 ...
• 559
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. ...
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 ...
• 1,400
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 (...
• 2,454
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 ...
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 ...
• 397
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 ...
• 151
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 ...
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 ...
• 1,112
1 vote
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 ...
• 547
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 ...
• 1,867
1 vote