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)

1
vote
1answer
108 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 ...
3
votes
1answer
257 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
2answers
49 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
2answers
360 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 ...
5
votes
3answers
187 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 ...
2
votes
1answer
307 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 (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-...
4
votes
1answer
467 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 -(void)callDfs:(int)...
0
votes
0answers
13 views

View the path a AI is walking along in Unreal Engine 4

I'm using unreal engine 4.12.4 and I want to be able to see the path that an actor will use when i trigger "Simple Move To Location" and i want to see the path as a line in game for testing.
1
vote
1answer
79 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 ...
1
vote
1answer
40 views

What's an optimal procedure to create a connected cyclic grid of nodes and edges for A* pathfinding

like the title says, I'm trying to create a grid of nodes that hold edges or connections to each other so I can perform A* algorithm to have objects traverse across them as seen in your standard RTS. ...
1
vote
0answers
63 views

How to implement A* pathfinding for enemies to follow player

The enemies in my game are supposed to follow the player in order to cause damage to it. Right now I have it where the enemy just goes in the direction that will bring it closer to the player, and ...
0
votes
0answers
19 views

UE4 Navmesh precision

I'm trying to make my very tiny man pathfind his way through a map of a school but the navmash won't recognize some of the hallways cause they are very narrow like this. So as you can see the man ...
3
votes
1answer
49 views

Multilevel 2D grid graph and A*

I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill. ...
1
vote
2answers
84 views

Using my pathfinding more efficiently

I'm making a roguelike in C# with the Roguesharp libraries, in which the map can be as large as 200x200 cells. When I have an entity requiring pathfinding, I am using Roguesharp's built in pathfinding ...
3
votes
0answers
240 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 ...
3
votes
1answer
250 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 ...
4
votes
2answers
115 views

Object outlining

I have an object whose boundaries can be define using a convex collider. I have an AI which needs to outline that structure to patrol it. The object is dynamic and composed of pieces like LEGO, each ...
0
votes
1answer
80 views

How to avoid 2d enemy using trigonometry?

I'm making a game in Javascript & HTML5. I have a "bullet" (let's call it so) that needs to reach the enemy (at fixed position) and that need to avoid the enemy's "bullet". To make the bullet ...
3
votes
2answers
143 views

GameMaker : how can i get the instance ID of multiple instance in a radius?

GameMaker and coding noob here, need help on something maybe trivial for some of you. I'm working on the map part of a game. I have a map with spots on it, each spot is an instance of the same object....
8
votes
3answers
191 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 ...
0
votes
0answers
32 views

AI: Turn-Based Movement with 2 actions per Unit

I am currently building a turnbased tactics game. The Board is a small (about 4*6) tiled grid. The AI plans all moves of its units, each unit can move 2 times move and attack or attack at ...
4
votes
1answer
201 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 ...
2
votes
3answers
1k views

Game Maker: Studio - Make objects avoid other instances of same object with A* pathfinding

I have a game where there are multiple enemies who must chase a single player. I have pathfinding set up using the GML A* pathfinding with mp_grid and a path. However, these enemies can walk on top ...
2
votes
1answer
102 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 ...
1
vote
0answers
44 views

How can I make cars drive navigate an intersection without colliding?

I'm trying to create a 2D game with a traffic intersection: My car game-objects need to pass through the intersection without colliding with each other, and without stopping, if possible. How can ...
42
votes
11answers
20k views

What path finding algorithms are there? [closed]

I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
2
votes
4answers
629 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
168 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
50 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
73 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
275 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 path-...
1
vote
1answer
103 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
2answers
42 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
33 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 ...
0
votes
1answer
33 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
138 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 http://digestingduck.blogspot.com.by/2010/03/...
2
votes
1answer
174 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
73 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
103 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
82 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
80 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
338 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
90 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. ...
0
votes
0answers
39 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
249 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
29 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
69 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
78 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
390 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 ...