Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

learn more… | top users | synonyms (2)

56
votes
5answers
15k 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 ...
55
votes
11answers
5k 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.
48
votes
5answers
2k 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 ...
38
votes
11answers
15k views

What path finding algorithms are there? [closed]

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?
33
votes
7answers
13k 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 ...
31
votes
4answers
9k 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?
29
votes
6answers
3k 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
4answers
3k views

Is the Manhattan distance monotonic when used as heuristic function?

I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1. I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
24
votes
3answers
15k 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.
23
votes
12answers
4k 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 ...
19
votes
3answers
3k views

Why do some networked games use interpolation and some use pathfinding for remote movement?

This is a bit of an open question but I'd like to see someone contribute a good reasoning for both. For a quick example of both: Interpolation Model Think the Valve model where the client is ...
18
votes
6answers
2k 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 ...
17
votes
7answers
2k views

How do I make A* agents avoid other agents?

I'm implementing a multi agent A* algorithm on a tile map. Agents move only in the X and Y axes. I avoid collisions between them by checking where the others are when calculating paths. It works fine ...
16
votes
6answers
788 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
943 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
3answers
6k 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 ...
14
votes
9answers
5k 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 ...
14
votes
4answers
3k 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.
14
votes
2answers
855 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 ...
14
votes
6answers
1k 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 ...
13
votes
1answer
1k views

How does the Simple Stupid Funnel Algorithm work?

Working with the funneling algorithm shown on Digesting Duck I'm not sure how the detection of the funnel works. Can someone explain the method clearly to me or suggest an alternative way of ...
13
votes
1answer
4k 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 ...
13
votes
1answer
1k 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 ...
12
votes
3answers
835 views

How to make natural-looking paths with A* on a grid?

I've been reading this: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html But there are some things I don't understand, for example the article says to use something like this for ...
11
votes
3answers
3k 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 ...
11
votes
3answers
1k 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 ...
11
votes
4answers
766 views

How to determine range of possible movement in turn-based, distance-based strategy game?

I'm creating a 2-dimensional, turn-based strategy game using c++ and SFML-2.0. Movement is distance-based rather than grid-based, with several different triangle-shaped pieces that, on a given turn, ...
11
votes
4answers
952 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
395 views

Are there any pathfinding algorithms that would handle different movement types?

I'm developing a bot for a BattleTech board game simulator http://en.wikipedia.org/wiki/BattleTech, it is turn based. The board is divided into hexagons, each one has a different terrain type and ...
11
votes
1answer
2k 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. ...
11
votes
1answer
2k 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 ...
10
votes
5answers
2k 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 # # # ...
10
votes
1answer
441 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 ...
10
votes
2answers
2k 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 ...
10
votes
2answers
1k views

What kind of steering behaviour or logic can I use to get mobiles to surround another?

I'm using path finding in my game to lead a mob to another player (to pursue them). This works to get them overtop of the player, but I want them to stop slightly before their destination (so picking ...
10
votes
2answers
3k 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: ...
10
votes
5answers
632 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 ...
10
votes
4answers
870 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
2k 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 ...
10
votes
2answers
371 views

How can I compute the shortest path in Euclidean environments with non-convex polygons?

Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles?
10
votes
1answer
1k 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 ...
10
votes
1answer
1k 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* ...
9
votes
7answers
496 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
5answers
922 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 ...
9
votes
3answers
899 views

Finding possible moves for an entity in a 2d tiled game

I'm having issues coming up with a specific search term for this, but how would one go about finding the possible moves in a 2D turn-based strategy game (i.e. FF:Tactics, Fire Emblem, Advance Wars). ...
9
votes
3answers
291 views

How to pathfind over an obstacle?

How to represent the following situation best - agent (@) needs to get to the goal($). The path is blocked by a moat(~~~). A rake (or some other device, like waterwalking boots) is available that will ...
9
votes
2answers
478 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 ...
9
votes
1answer
2k views

2D pathfinding - finding smooth paths

I was trying to implement a simple pathfinding, but the outcome is less satisfactory than what I intended to achieve. The thing is units in games like Starcraft 2 move in all directions whereas units ...
9
votes
3answers
3k 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. ...
9
votes
1answer
360 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 ...