Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
45
votes
5answers
5k views
How does Dwarf Fortress keep track of so many entities without losing performance?
In Dwarf Fortress you can have hundreds of Dwarves, animals, goblins, etc in game at any one time, each with their own complex AI and pathfinding routines. My question is how does this not produce ...
45
votes
11answers
3k views
How does A* pathfinding work?
I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
33
votes
4answers
852 views
Pathfinding for fleeing
As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B.
But how do I calculate a path when an object is at ...
32
votes
11answers
4k views
What path finding algorithms are there?
I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
27
votes
7answers
7k views
How does pathfinding in RTS games work?
[crossposted from stackoverflow]
In a game such as Warcraft 3 or Age of Empires, the ways that an AI opponent can move about the map seem almost limitless. The maps are huge and the position of other ...
27
votes
6answers
2k views
what is the standard solution to pathfinding towards a moving target?
I am working on a 2D RTS like game, basic A* works perfectly for moving a unit from point A to point B.
But now I facing the continuous path-finding problem, like A attack a moving object B, call A* ...
24
votes
3answers
4k views
How does Flow Field pathfinding work?
Supreme Commander 2 has something called flow field path finding. How does it work? Is there some article available I can read up on how it works?
21
votes
3answers
7k views
How does Navigation Mesh path-finding work?
I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
16
votes
6answers
619 views
Making the AI take different paths to each other
I have a top down 2d game where the AI spawn at the edges of the map and run towards the center.
I'm using A* and a node mesh to do the pathfinding.
Right now, the AI spawn at a point on the edge of ...
16
votes
7answers
827 views
Spawning units in a world made by Perlin noise?
There's some issues that I've come across in my Perlin noise-based game. Take a look at the attached screenshot below.
The white areas you see are walls, and the black areas are walkable. The ...
15
votes
6answers
1k views
AI control for a ship with physics model
I am looking for ideas how to implement following in 2D space. Unfortunately I don't know much about AI/path finding/autonomous control yet.
Let's say this ship can move freely but it has mass and ...
13
votes
9answers
4k views
Dynamic pathing algorithm for tower defense game
I'm making a Tower Defense and I need a good pathing algorithm for it.
I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or ...
13
votes
3answers
2k views
Are square or hex grids better for pathfinding?
Is there any significant difference between using a square or hexagonal grid for the area searched by a path finding algorithm. In other words, is square or hexagonal better, and if so why.
13
votes
6answers
542 views
How to make my characters turn smoothy while walking on a path(list of coordinates)?
I have a list with coordinates - output from A* algorithm - and I would like to make my characters smoothly follow this path with rotations.
So I have something like A and I want to get C
How can ...
12
votes
2answers
432 views
Partially observable game map — is A* appropriate?
I know very little about game development and I'm trying to wrap my head around pathfinding algorithms.
Consider this setup: an agent is on a 2D map and must find the shortest path to a globally know ...
