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)

2
votes
2answers
64 views

Efficient use of pathfinding

I'm doing a post-mortem on my game project, and this problem kept bugging me as my team couldn't solve it throughout. So my game is a pure 2D top-down shooter built with Unity3D, with enemies ...
3
votes
1answer
47 views

Pathfinding: longest route along tiles of same type

I'm programming a simple tile-based puzzle game, and I've gotten stuck trying to work out a pathfinding algorithm. Here's how the game is set out: The game board is (arbitrarily) 8 tiles wide by 8 ...
2
votes
0answers
45 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
3answers
120 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 ...
0
votes
1answer
22 views

How to identify entrances of a cluster in HPA*?

Recently I've become interested in understanding and implementing HPA* in a RTS game. I've found the following presentation which is really good for explaining how HPA* works: ...
1
vote
1answer
52 views

Pathfinding on multiple grids connected through teleports

I try to create a "AI" that can move independently on a map structure where the individual maps are only connected by one directional teleport squares (links). There are some map areas you can only ...
7
votes
1answer
133 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, ...
3
votes
1answer
106 views

C++ A Star Algorithm [path takes wrong route] using <deque> & unique_ptr

I am having issues, trying to get my A Star algorithm working, the main problem is with my process of the algorithm, I am using something known as the TL engine which has some of its own datatypes and ...
0
votes
1answer
27 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
52 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 ...
3
votes
1answer
61 views

How can I remove unnecessary nodes from my path?

How do I remove the unnecessary nodes from the path to make it as short as possible? Idealy I'd like the result path to look like the green line. The red thingy is not walkable. var ...
7
votes
2answers
207 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 ...
1
vote
1answer
66 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 ...
1
vote
0answers
26 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
32 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 ...
5
votes
3answers
148 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 ...
1
vote
2answers
68 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 ...
3
votes
1answer
122 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 ...
2
votes
1answer
52 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
64 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
60 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
1answer
134 views

How to choose and scale heuristics for A-star on a graph?

I am trying to find the best and scale my cost function for my algorithm. I am following amit blog which explain that ...
0
votes
0answers
13 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, ...
3
votes
1answer
114 views

Graph search with a high number of actions

I have implemented A* to reach a goal state from a start state. My state is position X,Y, angle and others state variable. I have a number of actions. What I call actions is : A* on a grid has 4/8 ...
4
votes
3answers
252 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
215 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 ...
3
votes
0answers
115 views

How to get NPC to Find and Follow Path to other NPC?

Problem: I am using Skyrim Creation Kit to create a very simple mod. I want the mod to make one NPC follow another NPC. My first problem is that I am not really 100% sure where to start. The second ...
0
votes
0answers
96 views

Code sample on how to implement Lee's visibility graph

In my recent search, I've been amazed about how difficult it is to find code examples or information on how to build visibility graphs. Considering its importance on video-game development for AI ...
0
votes
2answers
56 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
1answer
133 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 ...
3
votes
1answer
154 views

Local avoidance together with any-angle types of A* Pathfinding

Recently I have been implementing the Block A* any-angle path-finding algorithm in a project I have, for which I need extremely efficient results due to the large number of NPCs. However, I still do ...
1
vote
1answer
178 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
62 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 ...
2
votes
1answer
97 views

Pathfinding over a moving platform

I have beens struggling with the following. In the game I am developing with Unity 5 in C#, I need to implement basic pathfinding over moving platforms (not with moving platforms). It means, I am not ...
4
votes
2answers
135 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
81 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 ...
0
votes
1answer
91 views

Funnel algorithm

I'm implementing the funnel algorithm for pathfinding. After searching many resources I found those : https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf ...
0
votes
1answer
69 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: ...
9
votes
2answers
699 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

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 ...
0
votes
1answer
79 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
70 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 ...
1
vote
3answers
240 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 ...
3
votes
4answers
152 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). ...
0
votes
3answers
166 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
votes
1answer
80 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, ...
0
votes
2answers
62 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][ ][ ][ ][ ] [.][ ][ ][ ][ ] [.][ ][ ][ ][ ] [.][ ][ ...
8
votes
2answers
411 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 ...
3
votes
2answers
185 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
58 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 ...