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)

3
votes
2answers
55 views

How do I calculate paths for objects with limited acceleration?

For example, say I have a car and a car has a specific minimum turning radius and I want to drive that car from point a to point b, but the car isn't facing point b. How do I compute a path to point ...
1
vote
1answer
33 views

Doubts on player movement strategy

What I want to achieve is the player moving to the touched position on a 2D grid-based game, stopping at the last reachable spot if the target position is unreachable. What is the strategy usually ...
3
votes
1answer
152 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 ...
3
votes
1answer
201 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 ...
2
votes
4answers
530 views

Why is my A* Pathfinding incredibly slow?

I'm trying to use A* to make my enemies move about, but it takes up to 20 seconds to get a path to walk. My grid is only 64*64. This is my code: #include "AStar.h" #include "Node.h" #include ...
0
votes
2answers
140 views

A* pathfinding takes too long, shortcuts needed

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* path-finding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 ...
1
vote
1answer
84 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 ...
1
vote
2answers
23 views

How do I handle objects with a width and height in grid-based pathfinding?

I'm using the Jumper library for Love2D to do grid-based pathfinding, which worked fine until I wanted to make larger enemies (with larger collision boxes). How do i do that? My initial idea was to ...
3
votes
1answer
178 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 ...
1
vote
1answer
43 views

Circular fighter motion algorithm

Is there an algorithm to make ships take semi-circular patterns? I need something like the below image: Big Blue- Command Ship Small blues - fighters Red lines - path of movement I want the ...
3
votes
1answer
60 views

Locust Swarm algorithm for path finding (devour and move on)

I need to model a locust swarm that devour food stacks and move on to next stacks. I searched for articles and found few articles. These papers is about optimization applications but I want to convert ...
0
votes
0answers
200 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 ...
3
votes
2answers
320 views

Aligning pathfinding to the center of tiles?

I'm looking to achieve tile by tile movement in a project I'm working on. I employed the use of the asset Simply A* Path-finding to allow a unit to navigate the terrain. Since the tiles are ...
2
votes
1answer
83 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 ...
3
votes
1answer
434 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS ...
1
vote
1answer
83 views

Pathfinding to unknown destination point

Usually you need path finding algorithms to find one or the best path between two points. Do you know if path finding algorithm where you don't know the destination point exists? I have a graph made ...
0
votes
1answer
214 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
2answers
38 views

Movement looks funny If player takes up multiple tiles in tile-based game

So here is my problem: Start = +++ +++ +++ End = --- --- --- Player = *** *** *** +++000000000000 +++000000000000 +++000000000000 000000000000000 ...
0
votes
0answers
23 views

How do I turn a vector map into a nav mesh?

I have the following path finding problem: I have a map that is described as a set of polygons that are traversable and need to somehow write path finding for the system. The current data is that the ...
3
votes
1answer
130 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 ...
0
votes
1answer
29 views

Following waypoints, condition is never fulfilled

Given a 2D-grid which is defined like below and is used to draw a grid consisting of cells: int[,] grid; //filled with 0 (blocked) and 1 (walkable); I also have a A*-algorithm implemented which ...
2
votes
2answers
127 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 ...
2
votes
1answer
146 views

How can I adapt A* pathfinding to work with platformers?

I have an A* implementation that works in "top down" situations where gravity is not taken into account for pathfinding. But, I am looking to modify to work in a 2d platformer situation. I am using ...
1
vote
1answer
53 views

Should I use the pathfinding client side or server side? [closed]

I'm developping a game where the user can walk in a room (with the others players). There are some obstacles that blocks the user. I'm using a Javascript pathfinding library to find where the user can ...
0
votes
2answers
87 views

Dijkstra's Algorithm - Infinite loop

While running Dijkstra's Algorithm to assign a direction to every tile and when an object land on the tile, follow the direction to a goal. I encountered an infinite loop (or I think it is). The ...
0
votes
1answer
60 views

An algorithm for forming unit groups

Currently in my game engine when a user selects a large number of units and commands them to a target each unit finds its own path using Jump Point Search. The performance of this is generally OK. ...
2
votes
1answer
51 views

Forward A-star pathfinding vs Reverse A-star pathfinding

Under what condition does doing Forward path finding or Reverse pathfinding get better result? Most tutorials for open grid tower defence games says to pathfind from the Goal to the monster. Why is it ...
6
votes
1answer
1k views

How can I generate a (relatively) linear dungeon path?

We developing a concept for an action side-scroller. What we need is a way to generate a (relatively) straight map. By this I mean something like... It's clear to see that this map follows one ...
1
vote
2answers
71 views

Is it possible to use nav-mesh in 2d game in Unity?

I'm working on game that needs navigation and obstacle avoidance. I've used nav-mesh on 3d project before but now I'm trying to use it in 2d sprite game but it seems like it doesn't work. I want to ...
0
votes
1answer
79 views

Enemy shake/vibrate when following character

I am using the arongranberg A* path finding project to create way points for one enemy to follow the player. However, the enemy vibrates back and forward by about 0.1 - 0.2 unit distance when moving. ...
1
vote
0answers
60 views

Efficient pathfinding for flying actors through connected AABB volumes

I have created a concise graph of AABB volumes to use as the navigation volume for flying AI. They span the empty space around geometry: Here is a preview for one of the nodes - the central node ...
0
votes
0answers
32 views

HPA* on weighed (non-uniform) 2D grid maps

I'm researching pathfinding algorithms on the 2D grid maps in regard to their performance/memory consumtion. I'm particulary interested in the weighed maps as something much close to the reality than ...
5
votes
1answer
199 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 ...
1
vote
0answers
24 views

Automata Editor

I'm currently developing a State machine editor as a tool for some games my team is developing: but the algorithm I chose to display the paths between the states doesn't care about the obstacles, ...
4
votes
1answer
67 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 ...
1
vote
1answer
61 views

Dijkstra's algorithm null hypothesis pathfinding without navmesh

I am having trouble understanding how to implement dijkstra's algorithm for a path finding assignment, here's what the layout looks like: Each node has a List of neighbours which are found using ...
2
votes
1answer
374 views

Pathfinding and clusters

For an assignment, I am required to implement an A* algorithm in order to find the shortest path between two object using different heuristics null, this effectively becomes Dijkstra Euclidean ...
3
votes
1answer
121 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 ...
3
votes
2answers
97 views

Efficient use of pathfinding [closed]

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 ...
5
votes
3answers
168 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 ...
4
votes
3answers
160 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
36 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: ...
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
273 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
149 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
722 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. ...
0
votes
1answer
68 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
54 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
76 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
678 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 ...