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)

51
votes
11answers
4k 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.
53
votes
5answers
9k 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 ...
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* ...
10
votes
2answers
2k 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: ...
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 ...
11
votes
3answers
681 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 ...
28
votes
7answers
9k 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 ...
6
votes
1answer
8k views

Path finding algorithms?

I posted this question on stack overflow first, but I guess no one is very interested in video games there... What are some path finding algorithms used in games of all types? (Of all types where ...
3
votes
1answer
195 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS ...
7
votes
2answers
2k 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 ...
4
votes
4answers
433 views

How can I make my units follow predetermined paths?

I'm planning my first game and am planning on using the engine set out in Beginning Android Games, as it deals with a load of stuff that is just noise at the moment to me (because I've no real world ...
3
votes
3answers
3k views

Pseudo-code examples of A*?

I'm looking for pseudo-code examples of the A* pathfinding algorithm that actually works. I tried plenty of different ones where it's not really clear how to implement them at all times. Keep in mind ...
38
votes
4answers
1k 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 ...
12
votes
3answers
4k 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 ...
37
votes
11answers
8k 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?
14
votes
6answers
863 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 ...
16
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 ...
22
votes
4answers
2k 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 ...
16
votes
6answers
719 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 ...
12
votes
1answer
3k 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 ...
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. ...
24
votes
3answers
10k 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.
10
votes
3answers
2k 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
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* ...
7
votes
5answers
3k 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. ...
4
votes
1answer
324 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 ...
3
votes
1answer
2k views

A* pathfinding for an isometric map

I am making an isometric tower defense game in XNA and trying to implement the A* pathfinding algorithms for my enemy AI. I am quite new to programming, especially AI and pathfinding, so please excuse ...
3
votes
2answers
573 views

Multi-tile agent path-finding algorithm?

Suppose we have a uniform rectanglular grid as shown below. The a is an agent, o is obstacle and g is goal. What are the options of handling multitile agents (e.g. dragons or tanks)? . . . . o . ...
10
votes
1answer
947 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 ...
6
votes
4answers
2k views

Smoothing found path on grid

I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
5
votes
1answer
608 views

Pathfinding with 2D, non-grid based movement over uniform terrain

I'm looking for the best solution to pathfinding in my game. The map is ultimately grid-based, but entities are positioned using floats, and can move in any direction to any point on the map. The ...
3
votes
2answers
365 views

Working with chunks of terrain

Let's take for example that in our game, we divide our world (1000x1000 tiles) into chunks of 100x100 tiles. Each chunk contains its own npcs, traps, players, items, whatever. Now, there comes to my ...
2
votes
1answer
291 views

Seek Steering Behavior with Target Direction for Group of Fighters

I am implementing steering algorithms with group management for spaceships (fighters). I select a leader and assign the target positions for the other spaceships based on the target position of the ...
2
votes
4answers
963 views

Efficient path-finding on 2D tile-based multilevel map

It's a question I've been thinking about for some time... How do you effiently find a path on a 2D tile-based multilevel map? The map I use, for example, is 2048 on 2048 tiles wide. It has 14 levels ...
8
votes
2answers
369 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 ...
4
votes
1answer
303 views

Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of ...
2
votes
1answer
869 views

Enemy Movement AI

I have a non-tile-based top down shooter game, and I have enemies set up. However I need the enemies to move to the player. Pathfinding algorithms will mean the enemies will just hug the wall. The map ...
1
vote
2answers
397 views

Influence Maps for Pathfinding?

I'm taking the plunge and am getting into game dev, it's been going well but I've got stuck on a problem. I have a maze that is 100x100 with 0,1 to indicate if its a path or a wall. Within the maze ...
7
votes
1answer
1k views

Techniques for (literally) cutting corners on square grid maps

My game involves a level with deformable terrain and units that can travel in any direction but are slowed down by uneven terrain. Normal A-star should work fine in most cases, except on flat land ...
5
votes
1answer
124 views

trapped inside a Graph : Find paths along edges that do not cross any edges

This is a graph based platformer level and the round shapes are creatures. I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the ...
4
votes
2answers
2k views

How to handle pathfinding on a non-grid/non-node terrain map

I'm not sure if this is even path-finding. All I have is a 3D map that has hills, etc. I'd like the enemy to flock an object, but also walk around other objects. These blocking objects may be added ...
3
votes
3answers
449 views

Group arrival steering

I've got group movement implemented pretty much like this: http://www.red3d.com/cwr/steer/CrowdPath.html Basically, that's combining path following and separation. It works nicely as long as units ...
3
votes
1answer
566 views

A* PathFinding Poor Performance

I'm getting poor performance in-game due to my path-finding algorithm. The farther I get from my NPC, the worse the framerate gets. Ok, I updated my code and implemented the openList as a min-heap ...
3
votes
2answers
686 views

Infinite loop during A* algorithm

The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate ...
2
votes
1answer
167 views

how do I make an enemy target an ally unit?

I have 2 different classes, a EnemyFighter class, and a EnemyBomber class. both are planes that I have that can fly around the map.( i also have AllyFighter, and AllyBomber) So far they can follow ...
2
votes
2answers
685 views

pathFinding performance in Unity3d

I am making Sniper game in unity 3d. In this game zombies will come randomly towards the sniper and sniper have to kill them. I am using RAIN(indie) for path finding. It works best when zombies are ...
2
votes
3answers
404 views

Best way to implement mouse-based movement in MMOG

I want to design an MMO where players click the destination they want to walk to with their mouse and the character moves there, similar to Runescape in this manner. I think it should be easier than ...
2
votes
2answers
851 views

Are there any usable performant path-finding libraries for python?

This is cross-posted from StackOverflow, please feel free to answer there too: I'm working on a real-time isometric RPG in python, and wish to target mobile devices as a platform. The main area where ...
1
vote
1answer
258 views

How can I change the path a sprite is following in real time?

Is there a common way to implement a character following path that is issued and replaced in real time? For example: the character follows a path issued, and while it's on that path, if a new path is ...
0
votes
1answer
279 views

How do I make A* check all diagonal and orthogonal directions?

I'm making a turn-based tactical game and I'm trying to implement the A* algorithm. I've been following a tutorial and got to this point, but my characters can't move diagonally up and left. Can ...