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)

26
votes
3answers
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.
7
votes
2answers
343 views

2D A* Path-Finding

I have this problem, which isn't really a problem, but I feel like it's some sort of glitch in my code maybe. My pathfinder, to find a path from A to B, does this: which is almost fine, it works ...
7
votes
1answer
154 views

Cossacks game pathfinding

Cossacks (released in 2002) is an RTS game where you can build huge (few thousands men per player) armies on a really big maps. Imagine Age of Empires 2 for few players on Ludikris map with no lag, ...
9
votes
2answers
749 views

A* pathfinding for dynamic obstacles and player made blockages?

Hi I'm creating a TD in Unity 5 and need some help with my Pathfinding. I'm going to use Arons A* pathfinding for my AI which enables me to use dynamic objects and update the path during run-time. ...
1
vote
1answer
79 views

FollowPath steering behavior

I'm having a problem with AI movement in my top-down game. AI builds path and than moves using libgdx FollowPath (this problem is still actual) steering behavior. I have some solutions, but can't ...
0
votes
1answer
55 views

Calculate Jump Limits

My question is in a similar vein to this question, I am creating a pre-mapped pathfinding solution much akin to how Ash Blue was for my 2D platformer-style game (in XNA). As part of the process, I ...
1
vote
1answer
81 views

How do I structure AI that uses both Behavior Trees and Pathfinding?

Architecturally, what are the best practices for how these two concepts interact with each other? For instance, say I have an asteroids like game where the AI player must dodge floating asteroids ...
3
votes
2answers
700 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 ...
3
votes
1answer
133 views

Effective AI for 3D Motion

I am developing a game in XNA and am trying to create an effective AI for the enemy and friendly spaceships but am having a hard time keeping the game effective without disadvantaging one side or the ...
1
vote
0answers
31 views

Aron Granbergs Unity Pathfinding AI goes back and forth

The agent goes back and forth after calculating the path with seeker.StartPath (transform.position,target.transform.position, OnPathComplete);. The gizmo shows the correct path. Please watch this ...
2
votes
1answer
35 views

Add navigation obstacles during runtime lags

Please watch this short video. http://screencast.com/t/vw2a5FdOOT It shows the problem. It's using the build in Unity navigation and followed the guide to build the demo in the video. Everytime I ...
1
vote
2answers
70 views

Pathfinding assistance

Here's a quick image: I've generated a navmesh for my game that shows how an AI can get to each of its possible neighboring tiles in a map. (I followed some gamasutra article as reference, I'll ...
4
votes
2answers
163 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 ...
2
votes
1answer
122 views

Given a 3d goal point and a turn rate in radius, find max speed to reach goal

I'm working on a 3d space sim with AI agents flying ships through space. I am trying to get them to follow a waypoint path nicely, which involves figuring out how fast they can be travelling and still ...
3
votes
1answer
236 views

How to implement visibility graph pathfinding in Unity/C# to detect paths (i.e. visibility connections) efficiently?

I am struggling with implementing continuous path-finding trough visibility graphs. Notice, I know that grids can be used even when movement is not trough grids (e.g. Theta*). But for my current needs,...
2
votes
1answer
64 views

Storing visibility graph for path-finding: do redundant and non-visible pairs of points have to be saved?

Using C# in Unity, I have recently implemented an algorithm that determines during run-time the visibility graph of a given scene in my game project (visibility between corners of obstacles). Now I am ...
2
votes
1answer
101 views

Where/how should A Star tie breaking occur?

I've recently written a path finding script that utilizes a basic implementation of the A Star algorithm. It works fine but is not very fast. This is due, at least in part, to the fact that it isn't ...
1
vote
1answer
88 views

Find shortest path (quickly) on the surface of a 3d model?

Imagine this scenario: we have a 3d model, for instance a doughnut, apple or an orange (possibly something more complex). There's an insect (let's say an ant) on the surface of that food item. Now ...
0
votes
0answers
21 views

Identifying transitions and entrances in HPA*

I lack reputation to post more than 2 links, so I'll be squeezing the images I planned to add into one link. http://pastebin.com/6ZqGPNZ5 I've been trying to implement HPA* over the last few days, ...
12
votes
2answers
4k 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: ...
5
votes
3answers
369 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
1answer
296 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 ...
0
votes
2answers
60 views

need a pathfinding algorithm from 1 column to another

grid contains weights and I need a max path sum from one column to another possible movement directions are (right, up & down only). Can Djikstra or A* help ??
3
votes
3answers
9k views

Is there a way to display navmesh agent path in Unity?

I'm currently making a prototype for a game I plan to develop. As far as I did, I managed to set up the navigation mesh and my navmeshagents. I would like to display the path they are following when ...
1
vote
1answer
230 views

Embed a real city in a game and use data to find and display paths [closed]

First of all this question is gigantic but it's mainly about Unity, maps, pathfinding, and real data. The problem. In my game the player sees the map of a real city (in 2D), it’s exactly the same ...
0
votes
0answers
85 views

Jump Point Search with Weights

Everywhere I've searched on the internet, people seem to assume that jump point search would not work with weighted grids. So why wouldn't it work with this simple modification to the algorithm: This ...
0
votes
1answer
105 views

How to configure A* for large 2D Grid based pathfinding, where paths could be long or short?

I thought A* was Optimal, meaning I'd always get the quickest path. I have written a generic Pathfinding implementation here: https://github.com/mGuv/mGuv/blob/PathPerformanceExperiment/mGuv/mGuv/...
1
vote
2answers
624 views

Best way to constrain character to a path?

I'm in the process of developing a level-based runner for mobile phones, and I've hit a wall when deciding which method to use to get the character to move through the level. Basically - I need my ...
5
votes
1answer
453 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 ...
0
votes
3answers
230 views

Pathfinding to find the route to nearest resource in 2D grid

The setting is a game in a 2D gridlike labyrinth/maze. I'm looking at pathfinding algorithms such as A* and Dijkstra. I can't figure out how to have my game characters find the nearest resources. All ...
1
vote
1answer
98 views

A* Pathfinding math for 2D, oblique style game

I'm making a 2D, oblique-styled RPG game and am implementing A* pathfinding for NPCs. The game is on canvas, using melonJS engine and sprites not confined to a 'grid'. I'm having a hard time ...
1
vote
3answers
454 views

AI Random Path Genenrating

I would like to make an enemy walk randomly around a map I have made and if the player is in his zone of sight the enemy to change state to attacking/following. So how would I accomplish something ...
0
votes
1answer
114 views

A Star pathfinding on oblique map

I'm making an RPG and want to make npc ai to navigate the city. I am using polylines for collision detection, and my map is 2D, but oblique styled. I am considering using the A* algorithm to help them ...
1
vote
1answer
74 views

A* Path Finding Loops Forever

For, hours, I've been following these instructions. public PathFinder(IntegralLocation loc, final int dest_x, final int dest_y) { boolean found = false; final List<Node> open = new ...
3
votes
4answers
170 views

Special Pathfinding Algorithm

I need help with following pathfinding Task: I have a grid (7x7 squares) and the starting square is always on the far left side (column 0) and its target is to reach the far right side (column 6). ...
9
votes
1answer
22k 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 ...
-1
votes
1answer
87 views

How can I can create a world that a player can easily get lost in? [closed]

I am a 3D environmental artist and I'm currently planning an independent passion game project of mine. I have the concept of crazy hallways that lead to the rooms that the player has already visited, ...
3
votes
2answers
10k views

Pseudo-code examples of A*? [closed]

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 ...
8
votes
2answers
530 views

Pathfinding and collision avoidance on mobile

Currently I'm developing a Diablo like game for mobile platform(iphone5+). A simple A* search will find the path, but collision avoidance still needs to be taken into consideration. There will be ...
0
votes
2answers
95 views

Traversing a pre-defined path with a delay in SFML - C++

I want the player to move smoothly & slowly through a vector of co-ordinates that define a path, below is an illustration of what i mean. [P][ ][ ][ ][ ] [.][ ][ ][ ][ ] [.][ ][ ][ ][ ] [.][ ][ ]...
3
votes
2answers
233 views

Path finding in 2D grid for objects that can rotate and bigger than one tile (Tetris)

I'm trying to check if there is a path between two locations in a Tetris board. On this question it tells how to account for different shapes: Path finding in grid for objects that occupy more than ...
0
votes
0answers
69 views

How do I efficiently generate all valid configuration spaces of a Tetronimo in Tetris?

This question is relevant to How can I do optimal pathfinding for a tetris piece, which assumes we already have a start and end state. How we can efficiently generate all those valid configuration ...
7
votes
2answers
589 views

How to reference a map position in code?

I'm coding a digital version of the Macao board game which has a flat map similar to below. Players have a "ship" which starts in the blue box and can follow the dashed lines in any direction/...
1
vote
1answer
87 views

Finding the “Important” nodes of a grid path

On a Navmesh Grid, all nodes are essentially vertices or turn-points so the returned path is efficient in that it only involves points where an entity must change its direction. A grid path, however, ...
0
votes
0answers
35 views

Making a node map with PNG alpha channels

I currently creating a 2d game that requires the usage of boats that travel from one country to another. The countries are individual objects with there own png. Nehow I've got the original map of the ...
0
votes
2answers
381 views

finding a path from one point to another with obstacles help

Im building a tile based game and im implementing my path finding algorithm. Currently, it can find a path from point A to point B with no problems. However, if there are obstacles between point A and ...
0
votes
2answers
137 views

A* Implementation Produces zig-zag in positive directions

I have an implementation of A* in Java. I followed this guide http://www.policyalmanac.org/games/aStarTutorial.htm. But I noticed that the paths generated where the goal is in the positive X and Y ...
-2
votes
1answer
74 views

Optimal trajectory of area exploration

I've got next problem. There is three objects: first one, with next characteristics: circular area of view, speed, drag coefficient; wind (or water current, doesn't matter; some sort of resistance) ...
2
votes
2answers
585 views

Basic Node Based Pathfinding

I am new to pathfinding but i have read and watched through some articles, blogs and videos about Pathfinding. Since those that i have read and watched from are mainly for RTS Games, Grid Based ...
1
vote
0answers
51 views

Grid Based AI Pathfinding [duplicate]

I'm creating a top-down RPG and I have the movement system set up for the player character - it is alike to Pokemon in the movement sense in that it looks smooth but it is aligned to a grid. Since I ...