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)

5
votes
3answers
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 ...
5
votes
1answer
2k views

How to do starcraft pathfinding?

I've been trying to figure out how to implement something like the pathfinding in Starcraft 2. I'm not looking for all the sophisticated features like flocking, queueing, etc. In fact I like how in ...
5
votes
1answer
163 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 ...
5
votes
3answers
528 views

How can I do optimal pathfinding for a Tetris piece?

Imagine a standard Tetris board (10x20) using the standard set of 7 tetrominos. Given a Tetris game state and a target position, how can I find the optimal sequence of moves that will get the ...
5
votes
3answers
1k views

A star pathfinding and discrete/smooth positions

The A* (A-star) algorithm usually represents a path on a grid. Once a path has been found, however, the path looks blocky and is not suited if you move your units with floating point datatypes. Here ...
5
votes
1answer
295 views

AI, Pathfinding - Searching Behavior

I'm developing a top-down 2D game mostly based off a tilemap/grid. The player will be able to build structures on this grid while other objects like vehicles will move around freely. I've been working ...
5
votes
2answers
854 views

How to create a curve from a set of points that passes through said points?

What is the best way to create a smooth curve path from a set of points? For example: I've seen Bezier curves before, but those try to smooth out the path from the set of points, like this:
5
votes
3answers
2k views

3D pathing finding with flying

Does anyone know of a (free or paid) solution that enables 3D path finding? Basically something like: CalculateRoute(input_geometry, start_pos, end_pos, variance) I found a good paper on the ...
5
votes
1answer
547 views

How can I plot a radius of all reachable points with pathfinding for a Mob?

I am designing a tactical turn based game. The maps are 2d, but do have varying level-layers and blocking objects/terrain. I'm looking for an algorithm for pathfinding which will allow me to show an ...
5
votes
1answer
268 views

A* for non grid network

For my specific case, I am trying to find a path finding implementation similar to what described here. I could see reference implementation for A* and HPA*, but I wonder how to extend A* to simple ...
5
votes
3answers
158 views

Find Minion with shortest path

I'm working on a game like Settlers III/IV. There are buildings which produce goods which have to be gathered by carrier units. I have to find the carrier with the shortest path to collect the ...
5
votes
4answers
254 views

How can I navigate to a target between bodies moving along fixed paths?

The problem: An autonomous ship starts at the outskirts of a solar system, and wants to move to a moving target, which is one of the planets. There are also many other planets moving at the same time, ...
5
votes
1answer
172 views

QuadTree-based pathfinding for a volume body

I want to make a game where a player follows a mouse pointer. The game is not tile-based. I use quadtree for a collision detection and everything works fine. But now I want to develop a player ...
5
votes
1answer
444 views

How does an AI determine the bearing to follow within a nav mesh?

I've done some reading on nav-meshes, and I understand how to generate a path of polygons to reach a goal. However, what I don't understand is how you determine the bearing to follow within each ...
5
votes
3answers
235 views

Pathfinding Search for Path of Specific Length

I am creating a roguelike. This question applies to random map generation. First, I generate areas using a BSP algorithm, where I randomly divide the map into areas. Then, I generate a graph of the ...
5
votes
1answer
301 views

What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how ...
5
votes
1answer
282 views

A* search in hexagonal grid with minimum turn radius

I need to run an A* search through a hexagonal grid. However, I have one nasty constraint: my vehicle can only turn so sharp. It has a specified minimum turn radius. I can't quite see how to translate ...
5
votes
1answer
371 views

A* pathfinding algorithm to identify entrances into current “room”?

Was looking for some online articles that might have a good idea or two in how to approach this but not finding much. Most of it deals with the various ways to generate and follow a path to a known ...
5
votes
1answer
219 views

AI pathfinding in mostly-free space

I'm working in an action/strategy proyect. Consider it a RTS game. The game is in 2D (with LibGDX), and I have a lot of soldiers moving along. Now I have to implement the AI. Let me say some things ...
5
votes
1answer
376 views

Dynamic navigation mesh changes

I'm currently trying to convert from grids to navigation meshes for pathfinding, since grids are either too coarse for accurate navigation, or too fine to be useful for object tracking. While my map ...
5
votes
1answer
211 views

Pathfinding avoid a list of polygon

i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very ...
4
votes
4answers
2k views

A* algorithm very slow

I have an programming a RTS game (I use XNA with C#). The pathfinding is working fine, except that when it has a lot of node to search in, there is a lag period of one or two seconds, it happens ...
4
votes
1answer
476 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 ...
4
votes
3answers
694 views

Find shortest path to gather items

I have a rectangular grid with obstacles and food items on certain tiles. There are also a few storage bins. Each food item gives 10 food. How can I find the shortest path that will allow me to ...
4
votes
1answer
734 views

How to determine that nodes in Grid Graph are unreachable before applying pathfinding?

I would like to determine accessibility of nodes before applying pathfinding algorithm to Grid Graph. I have a surface with nodes overlayed on it and I would like to somehow determine that nodes ...
4
votes
2answers
137 views

How should I use Monte Carlo method to simulate some police cars that keep patroling in a tile based map?

I have a tile map (isometric) and I have some police cars that they patrol all the time on the map, there is some building and other cars in map too so they are considered as constraints in my ...
4
votes
4answers
745 views

How can I make a character smoothly traverse a list of waypoints?

I want to set up paths for enemy characters in my game to patrol. I'd like to be able to define a list of waypoints and have the enemy follow the path from one point to another, but in a smooth curve. ...
4
votes
1answer
485 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 ...
4
votes
2answers
262 views

How would I go about updating my electronic circuit simulator's 'electricity'?

I have made an application which allows the user to place down wires, power sources, and inverters on a virtual circuit board. All connections between tiles are automatic, as shown here: As you ...
4
votes
2answers
2k views

How to create a thread in XNA for pathfinding?

I am trying to create a separate thread for my enemy's A* pathfinder which will give me a list of points to get to the player. I have placed the thread in the update method of my enemy. However this ...
4
votes
2answers
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 ...
4
votes
1answer
324 views

How to create a path-finding compatible road map from user input?

I'm currently working on an agent simulation (inspired by the recent SimCity release). Now, basically I understood how agents work but I do not understand how to put them into context. Agents travel ...
4
votes
4answers
2k 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 ...
4
votes
3answers
848 views

Pathfinding for a lot of units, mostly random movement

I'm using a uniform cost eight-directional grid as a map, with buildings that represent unpassable terrain - the map tries to simulate a top-down flat city. I'm trying to fill the city with randomly ...
4
votes
3answers
750 views

Creating the nodes for path finding during run time - more like path making and more

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question. It's a 2d turn-based ...
4
votes
2answers
1k views

Which pathfinding algorithm should I use for multiple enemies and tower placement?

I am new to game development and I am developing my first "Tower Defense"-type game. I need a pathfinding algorithm to place my towers and to move enemies. For tower placement case: I want the ...
4
votes
4answers
518 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 ...
4
votes
3answers
135 views

A* in 2D game. corner pathfinding issue

the issue I'm having will be best described with pictures more so than with code, so lets have a look if you will. So all the mobs followed the player and started attacking him, but as soon as 4 ...
4
votes
3answers
261 views

What is the most appropriate path-finding solution for a very large proceduraly generated environment?

I have been reading quite a bit in order to make the following choice: which path-finding solution should one implement in a game where the world proceduraly generated, of really large dimensions? ...
4
votes
1answer
118 views

Suboptimal A* Pathfinding Solution Example using Manhattan Distance Heuristic

I believe using an overestimating heuristic with A* is not guaranteed to find the shortest path. Assuming an agent can travel as a bird using euclidean distances, the manhattan distance provides just ...
4
votes
3answers
591 views

Unit turning in navmesh-based pathfinding

I'm working on an RTS game, and I'm using navmeshes for unit pathfinding. I do know how to find a general path within a navmesh, but how do you determine if the unit have enough space to turn? I ...
4
votes
3answers
3k views

Which algorithm used in Advance Wars type turn based games

Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to ...
4
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 ...
4
votes
2answers
919 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 . ...
4
votes
1answer
88 views

Cram search results into viewport (of a search minimap)?

I'm no coder, nor do I try to be. I just had one of those "it's impossible" arguments with folks who love to argue with me before they even understand what the argument is about :) So I need to ...
4
votes
1answer
102 views

Simplify navmesh path

I'm trying to implement pathfinding in my game, I'm using navmesh with triangles. I'm able to find a path but I want to simplify the path. This is what I have right now : Green quad is start ...
4
votes
1answer
122 views

How to achieve partial pathfinding?

Let's say I already have an A* algorithm. How can I handle the cases when the goal cannot be reached, and still attempt to get there? For instance on the following example: Notice the amazing GIMP ...
4
votes
1answer
266 views

How can I test if an object will “fit” during pathfinding?

I'm tinkering around with a 2d game where obstacles are polygons of arbitrary shapes, sizes and locations, and movable entities (players/enemies) can also be of arbitrary sizes. What's a good general ...
3
votes
6answers
890 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 ...
3
votes
1answer
523 views

How do I avoid pathfinding characters getting stuck in corners?

I used A* pathfinding to return a list of Tiles to get from an enemy to the player. After that, I wasn't sure how to actually move the enemy. What I ended up doing was get the first Tile in the path. ...