# Tagged Questions

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

19k 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 ...
7k 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.
3k 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 ...
19k 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?
16k 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 ...
10k 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?
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* ...
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 ...
19k 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.
4k 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 ...
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 ...
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 ...
3k 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 ...
834 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 ...
978 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 ...
6k 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 ...
8k 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 ...
4k 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.
885 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 ...
2k 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 ...
2k 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 ...
5k 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 ...
1k 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 ...
3k 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. ...
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 ...
4k 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 ...
4k 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: ...
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 ...
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 ...
919 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, ...
1k 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 ...
455 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 ...
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 ...
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. I'...
2k 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 ...
505 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 ...
1k 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. Instead,...
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 # # # ########...
462 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 ...
4k 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 ...
715 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 ...
934 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 ...
321 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 ...
4k views

### How to calculate the vector of an interception?

Given are a twodimensional space, and 1 friendly spaceship standing still, one foe is moving NOT directly to the friendly ship with known actual position, speed and direction. The friendly ship wants ...
544 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 ...
3k 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 ...
376 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?
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* ...