Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
46
votes
5answers
6k 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
869 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
5k 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
625 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
832 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
2answers
568 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 ...
13
votes
6answers
565 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
1answer
2k views
A* navigational mesh path finding
So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world ...
12
votes
1answer
578 views
Is nVidia's CUDA suited to performing pathfinding calculations?
I want to know if it would be worth executing pathfinding on the GPU (using nVidia's CUDA, or an equivalent) in certain situations, or whether it would be a wasted effort. The situation I imagine ...
11
votes
4answers
527 views
How do I get AI Agents to move along a curve?
Currently my very basic AI framework has agents that move along a a jagged path made up of a series of points.
They do this by simply moving their position from one point to the next. When they ...
11
votes
1answer
361 views
Pathfinding on a uneven planetary surface
My question is what would be the best approach to pathfinding on an uneven planetary surface?
Background Information
I have created a planet from displacement mapping 6 sphere projected planes. ...
10
votes
3answers
2k views
Real Time Dynamic Pathfinding?
I'm currently doing some pathfinding research and my simulation is the following:
I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
10
votes
4answers
668 views
How do I make NPC pathfinding look believable?
Is there an "academic" way to have NPC walking randomly on a map, but having a believable comportment ?
The obvious scenario is a armed guard who is walking around a basement to secure it. It's quite ...
10
votes
2answers
334 views
How to compute the shortest path in Euclidean enviroments with non-convex polygons
Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles ?
thanks
10
votes
1answer
680 views
Is precomputed pathfinding still relevant?
Context
Old Lucas Arts (ScummVM era) point and click graphic adventure games used precomputed pathfinding. Here's a rough outline of the technique.
Step 1
The floor in each room was divided into ...
9
votes
7answers
464 views
How should I replan A*?
I've got a pathfinding boss enemy that seeks the player using the A* algorithm. It's a pretty complex environment, and I'm doing it in Flash, so the search can get a bit slow when it's searching over ...
9
votes
3answers
1k views
Moving around/avoiding obstacles
I would like to write a "game", where you can place an obstacle (red), and then the black dot tries to avoid it, and get to the green target.
I'm using a very easy way to avoid it, if the black dot is ...
9
votes
3answers
489 views
Algorithm to see if two voxels are interconnected
I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to ...
9
votes
5answers
1k views
Longest path algorithm for roguelike maze generation
I have a simple grid-based map composed of rooms, like this (A=entrance, B=exit):
0 1 2 3
#########
0 #B# #####
#########
1 # ### #
#########
2 # # #
# # #
3 # # #
...
9
votes
2answers
514 views
Finding shortest path on a hexagonal grid
I'm writing a turn based game that has some simulation elements. One task i'm hung up on currently is with path finding. What I want to do is, each turn, move an ai adventurer one tile closer to his ...
9
votes
5answers
461 views
Situational awareness in path finding
Assume you had to find the shortest path through a dungeon, where certain passages are only opened to you after certain items were collected, like locked doors and keys, for instance.
The normal gut ...
9
votes
2answers
746 views
How do I implement group formations in a 3D RTS?
I managed to get pathfinding work for a single unit, and I managed to avoid agent-agent collision, but now I need to be able to send a group of agents to some location.
This is my set-up so far:
...
9
votes
1answer
545 views
Efficient path-finding in free space
I've got a game situated in space, and I'd like to issue movement orders, which requires pathfinding. Now, it's my understanding that A* and such mostly apply to trees, and not empty space which does ...
8
votes
5answers
921 views
Why is Reinforcement Learning so rarely used in pathfinding?
The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development.
...
8
votes
5answers
827 views
Slow performance on an A* implementation in a tower defense game
I'm making a Tower Defense game in Flash with no predefined path.
Although my grid is 40x40 (small?), A* is struggling when recalculating every time. So I made my own modification to ease the ...
8
votes
1answer
387 views
Locate the shortest path through obstacles when all normal paths are blocked
I'm making a Tower Defense and I have basic pathfinding working, but I got a problem.
I want to make the path blockable, and when a block occurs the runners will attack the blocking towers.
So what ...
8
votes
3answers
554 views
Should I share the same tile structure for display and pathfinding?
I know how to display a 2D map with tiles.
I know how to make a pathfinding algorithm using A*.
Those two things demand a structure or a class. My question is : do you use the same structure for ...
8
votes
2answers
1k views
pathfinding with obstacles in a Warcraft 3 like game
Consider A* searching on a tile based map. A straight forward code would be: If there is an unit inside that cell, then it is unreachable, this is ok.
But there is map resolution issue. When I look ...
8
votes
2answers
370 views
What alternatives exist of how an agent can follow the path calculated by a path-finding algorithm?
What alternatives exist of how an agent can follow the path calculated by a path-finding algorithm?
I've seen that the most easy form is go to one point and when the agent has reached this point, ...
8
votes
2answers
268 views
Drone targeting
Imagine a "drone" and a target point on a 2d plane. There are eight parameters:
P = my position
Q = target position
V = my velocity
I = my moment of inertia
w = my angular velocity
s = my angular ...
8
votes
1answer
591 views
What are the disadvantages and/or limitations of navigation meshes?
I have a lot of materials on navigation meshes, what they are, their advantages over graphs made up of waypoints, etc. However, I haven't seen much information regarding the limitations and the ...
8
votes
3answers
1k views
PacMan character AI suggestions for optimal next direction
Firstly, this is AI for PacMan and not the ghosts.
I am writing an Android live wallpaper which plays PacMan around your icons. While it supports user suggestions via screen touches, the majority of ...
8
votes
3answers
2k views
How do you do AI path following within a 2d physics engine like farseer/box2d?
I'm in the process of moving a 2d top down game I've been working on into a proper rigid body physics engine like Farseer. Up until now, I had just hacked together my own physics code where needed.
...
8
votes
1answer
180 views
Estimating costs in a GOAP system
I'm currently developing a GOAP system in Java. An explanation of GOAP can be found at http://web.media.mit.edu/~jorkin/goap.html. Essentially, it's using A* to plot between Actions that mutate the ...
8
votes
2answers
383 views
Tile-wide extent tracing on a grid
I'm currently working on A* pathfinding on a grid and I'm looking to smooth the generated path, while also considering the extent of the character moving along it. I'm using a grid for the ...
8
votes
1answer
776 views
Triangulation A* (TA*) pathfinding algorithm
I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81.
He describes how to adapt the regular A* ...
7
votes
5answers
2k views
Best pathfinding algorithm for a tower-defense game? [duplicate]
What do you suggest would be the best algorithm for a tower-defense game? It's a 2D based tile game, where there is walls and towers blocking the way, between spawnpoints and their destination points.
...
7
votes
2answers
478 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 ...
7
votes
2answers
454 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
835 views
Is Jump Point Search (A* with JPS) appliable to non-diagonal grids?
I'm trying to speed up my pathfinding and discovered A* with JPS. It basically prunes tiles before adding them to the OPEN set.
Can I use that technique with my grid that only allows straight ...
7
votes
2answers
677 views
What heuristics are used in NavMeshes?
What heuristics do programmers use in A* pathfinding for NavMeshes?
NavMesh = Navigation Mesh, its a type of pathfinding that uses meshes instead of waypoints.
7
votes
2answers
237 views
How to handle entity path-finding and movement in a large networked world?
Considering the image above with tiles split into 32x32 boxes, I have an entity which is marked to 'aggro' nearby players that come close to it. I'd like this monster to ideally chase the player (and ...
