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
4answers
2k views

One Step-Ahead A-Star

I am attempting to create a server-centric RTS (as opposed to usual parallel synchronised simulation route of most RTS games today) - however I am still leveraging the discreet N-turns-ahead paradigm ...
5
votes
3answers
233 views

A* : Partial recalculation when one node *changes*

I have implemented an A* library. Its most interesting feature is that it is "interruptible"; for example, you can stop the calculation loop on a game frame, and resume it later on the following ...
5
votes
2answers
533 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 ...
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
209 views

What is best method for 2D pathfinding in procedural world?

I have been researching path-finding for 2D games and would like to create a system that allows A* to perform as best as possible over a near infinite world. This system is intended to manage not only ...
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
167 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
356 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? ...
5
votes
3answers
632 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
2k 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
306 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
915 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
169 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
3answers
3k 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
572 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
279 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
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 ...
5
votes
1answer
235 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
452 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
282 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
335 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
286 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
376 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
274 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
397 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
236 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
502 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
716 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
795 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
150 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
900 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
505 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
265 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
3answers
161 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
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
388 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
897 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
801 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
523 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
1answer
146 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
656 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
2answers
972 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
2k 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 ...
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
1answer
68 views

How can I implement A* so that it accounts for the size of the actor?

I'm trying to make a little A* implementation using polygon verticies as nodes instead of grids and I ran into the problem of figuring out what paths are wide enough to accommodate the actor moving ...
4
votes
1answer
95 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 ...