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)

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
7answers
485 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 ...
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* ...
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 ...
6
votes
7answers
1k views

Wikipedia A* pathfinding algorithm takes a lot of time

I've successfully implemented A* pathfinding in C# but it is very slow, and I don't understand why. I even tried not sorting the openNodes list but it's still the same. The map is 80x80, and there ...
7
votes
2answers
887 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.
8
votes
5answers
999 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. ...
1
vote
1answer
711 views

Navmesh string pulling vs funneling

I'm creating a path-finder for navmesh. I'm wondering which method should I use after the A* has been completed, funneling or string pulling? What are the advantages/disadvantages of using them on a ...
3
votes
1answer
595 views

Sample Projects/Source for Navigational Meshes

Anyone aware of any sample source code that contain Navigational Meshes? I'm aware of recast navigation (which is a little bit too complicated). - Written in C++. Preferably C# but C++ is ok.
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 ...
0
votes
3answers
2k views

Node-Based pathfinding vs A* and others

Whats the difference between node-based pathfinding algorithm and the A* among others? A friend just told me about node-based, but I cannot find much tutorial or information on it.
2
votes
1answer
382 views

What tools are available for creating 3D collision and pathfinding data?

What is the process of creating geometry data to assist on NPCs movements and such on a 3D world to avoiding having them from going through the ground, etc? Are there specific modelling programs that ...
4
votes
3answers
842 views

What algorithm to use for path mapping?

I am making a turn based game with tiles, much like Final Fantasy Tactics. I am trying to develop an algorithm for mapping out a list of available tiles to walk on. So for example, I am at (0,0) and ...
5
votes
2answers
471 views

How do I apply A* to a complex and dynamic 3D environment?

So I've looked a bit at Breadth-First and Depth-First search algorithms and I think I've got a pretty good idea of how they work. Now I am here : http://www.policyalmanac.org/games/aStarTutorial.htm ...
10
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 # # # ...
28
votes
7answers
10k 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 ...
10
votes
4answers
806 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 ...
8
votes
3answers
589 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 ...
10
votes
2answers
368 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?
14
votes
3answers
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.
1
vote
2answers
239 views

What are some techniques used for mouse tracking, with a bit of “emulated lag”?

I am trying to implement a system, where the cursor (in my case the player's avatar) is always about 1.5 seconds (a configurable interval) behind where the mouse actually is. If I change the cursor's ...
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 ...
9
votes
5answers
891 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
1answer
424 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 ...
24
votes
3answers
11k 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.
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 ...
29
votes
4answers
7k 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?
3
votes
5answers
707 views

In what instances would you want to use path-finding algorithms other than A*?

I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right ...
53
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.
37
votes
11answers
10k 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?