# Tagged Questions

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

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 ...
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

### 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* ...
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 ...
2k 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 ...
1k 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.
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,...
937 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 ...
703 views

### Sample Projects/Source for Navigational Meshes [closed]

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.
4k 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 ...
3k 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.
403 views

### What tools are available for creating 3D collision and pathfinding data? [closed]

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 ...
1k 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 ...
534 views

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

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 ...
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 # # # ########...
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 ...
939 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 ...
631 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 ...
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?
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.
248 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 ...
2k 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 ...
948 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 ...
463 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 ...
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.
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 ...
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?
931 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 ...