A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [path-finding]

Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

59 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
2answers
734 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 simply ...
4
votes
4answers
180 views

2D Top Down: Can't follow the path accurately

In my game, there are many agents. Agents request a path, then after attaining a path to "goal" they follow the path. However player and many other things in the world can impact their position by ...
4
votes
0answers
153 views

Is there an algorithm to construct lines (sets of grid points which are all connected) from an unsorted set of grid points?

I have a 2d square grid used for pathfinding that I wish to convert into a navigation mesh. My idea is to pluck out all of the nodes that are on the edge of walkable space, simplify the amount of ...
3
votes
0answers
66 views

How to implement path-finding with a large number of blocking agents following similar paths?

I want to implement a demo like creeps laning in Dota 2. So for simplicity, there is Left team and Right team, they are enemies. Units from Left team move toward Right base, and units from Right team ...
3
votes
1answer
172 views

Which Pathfinding Algorithm is Best For My Case?

I'm creating a top-down space shooter game where there is no real "map" per say since there is no real terrain, but there are obstacles in the form of asteroids, other ships and a few circular ...
3
votes
0answers
764 views

How can I achieve dynamic pathfinding in Godot?

I am new to Godot and trying to implement dynamic pathfinding on a 2D map which includes both static obstacles and moving units. As I understand it, Godot's NavMesh makes it almost trivial to generate ...
3
votes
1answer
101 views

How to find the ideal path done inside a given shape in LibGDX?

I'm trying to make an android/libgdx game in which for every level you have a different shape as a png, and you have to drag your finger inside the shape and try to be as close as the ideal path ...
3
votes
0answers
98 views

Agent avoidance in 3D

I am currently trying to find some alogorithm for agent avoidance in 3D (or for simplicity, 2.5D could be enough). So far, I have been using variation of RVO - "Reciprocal Collision Avoidance" (C++ ...
2
votes
0answers
44 views

How can I implement caching into my Rectangular Symmetry Reduction pathfinding algorithm?

I have a working implementation of Rectangular Symmetry Reduction (see here and here for more information on RSR). I'm interested in further improving performance over raw A* by implementing caching ...
2
votes
2answers
84 views

Pathfinding: Searching through 3D neighbours given certain parameters C#

I'm currently new to the whole pathfinding thing (and coding in general thing), but I seem to have figured it out. It is 3D pathfinding, working on a 3d array of nodes. Everything works, but my ...
2
votes
0answers
24 views

How to modify A* so that it takes into account the number of movement point left?

Context : turn based game, grid system Let this graph here : (A)-2-(B)-1-(C) | /| / 1 2 2 1 | / |/ (D)-1-(E) My unit is at A and wants to go at C. ...
2
votes
0answers
254 views

How to go about implementing pathfinding in Unity with Tiled2Unity map prefabs?

I have created a map using Tiled application and have added collision boxes and used Tiled2Unity to import the map to Unity. The collisions are working with key ...
1
vote
0answers
36 views

Navigation Mesh, Chunks and Funnel Algorithm

I am building a little RTS-like game as a side project and I am currently working on pathfinding. My approach to pathfinding is heavily inspired by things I saw in the Starcraft II map editor, which ...
1
vote
1answer
24 views

Node representations in a navigation mesh

There are different ways to represent nodes in a navigation mesh. It's either along triangle centroid, along triangle vertices or along edge midpoints. As I understand if you choose triangle centroid ...
1
vote
0answers
17 views

Having difficulty integrating flow field with flocking algorithm

I have been tweaking my path-finding in my game for a while now, and it's mostly functional, but there are some major issues that are holding me up. I have a flocking algorithm implemented to help ...
1
vote
0answers
50 views

RTS Pathfinding without collision between units Options

Ever since I made my units move to a certain location a problem has popped up that of course if I try to make two or more units go to the same place they fight for the same spot. Am I just being ...
1
vote
0answers
52 views

Most efficient way to recalculate enemy A* path on the fly?

I'm working on implementing a more robust pathfinding algorithm for the enemies in my top-down shooter game, and I have the A* algorithm working, but now I need to decide when to calculate the path. ...
1
vote
0answers
20 views

Smoothing long paths with splines

What is the best way to smooth a long path with splines? I first implemented a Bezier curve but then realised that I would have to join a lot of them. I used A* on a weighted grid so I can't use ...
1
vote
0answers
14 views

Find out remaining distance before utilizing SetPath()

I am currently trying to find out the remaining distance of an object to the target point where I click at. However, CalculatePath() will only have a remaining ...
1
vote
1answer
70 views

How to Steer a Moving Object Away From Another Object(s)

I'm working with C# in Unity, and I'm making a top-down space shooter game in which there are many different AI-controlled ships flying around. The problem is that these ships often fly on top of one ...
1
vote
0answers
32 views

Find the optimal position minimising the total path cost to multiple goals (A-star without a starting position?)

I have a 2D grid of discrete tiles, where some tiles (W) are impassable. Given a number of goals (G), what is the best way to find the position that minimises the total cost to all the goals? Example:...
1
vote
1answer
404 views

Multi-level 3D grid based pathfinding in Unity

I'm trying to come up with a way to pathfind on multiple levels. See image: The orange walls would be considered a ladder, connecting you to the upper levels. At first I thought of looking at it as ...
1
vote
1answer
428 views

Line of Sight Check Theta* Algorithm

I am looking at implementing the Theta* algorithm in a 2D NavMesh. I have A* working, and I need to add a line of sight check to turn it into Theta*, this seems relatively easy in a uniform grid but a ...
1
vote
0answers
113 views

Is there an established way to create a 2D XY NavMesh in Unity?

Specifically, one in the empty space between colliders, rather than on an XZ plane (more or less) over the surface of a collider? Specifically this is because I have a drone, in a current project, ...
1
vote
0answers
200 views

Pathfinding towards a moving target in 2D Platformer

I have an enemy in my 2D platformer that chases the player around the level. I implemented a modified version of A* that works with gravity as described here: https://gamedevelopment.tutsplus.com/...
1
vote
0answers
137 views

Game “Hocus”: How to do the path finding?

I rebuild popular apps to get good at Godot. This game Hocus poses a challenge in terms of path finding. I have a solution, but as the illusions scale, it becomes ridiculously time-consuming to set up....
1
vote
0answers
177 views

2D Sideview Procedural Water Generation

How can I generate water in a procedural 2D sideview landscape? Here's what I currently have: First generate the heightmap of the land Then generate the water, based on the land Here's how I ...
1
vote
0answers
323 views

Best approach to smooth pathfinding for 2d top down game LibGDX

I'm trying to make a buddy ai that follows the player (being controlled by you) around and at the moment it works but when I add collision detection it doesn't work very well when the buddy hits an ...
1
vote
0answers
313 views

Simple Stupid Funnel Algorithm (SSFA) for 3D Navigation

tl;dr I need an algorithm similar to SSFA except for portals with 4 vertices (or n vertices if an algorithm like that exists). I'm working on a game that requires pathfinding in 3 dimensions. By this ...
1
vote
0answers
278 views

Letting an Pathfinding Algorithm generate movement paths for all possible Connections in a Starsystem-based Universe

First of all I want you to forgive me when I make mistakes in my writing, english isn't my first language, and also: If this is the wrong place to ask, please direct me to the right place then. So, ...
1
vote
0answers
286 views

Is Unity 5.6 NavMesh Data Available to Gizmos/Editor?

I have a script from Dungeon Architect that basically draws Gizmo lines along all connections between neighboring waypoints, which is nice. However, I'd like to draw a secondary line the follow the ...
1
vote
0answers
251 views

How to convert an octree to a 3D array

I have an octree that I'm planning to use for 3D pathfinding. My plan was to break down the world such that all the leaf nodes of the tree would be of equal dimensions that would create a nice grid ...
1
vote
0answers
124 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 I ...
1
vote
0answers
45 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, I'm ...
1
vote
0answers
95 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 ...
1
vote
0answers
840 views

Square tile navigation unity

I'm looking to generate a grid style navigation system in Unity. I have created a map in Tiled and am unsure how to continue considering the tiles will have different properties. The closest example ...
0
votes
0answers
14 views

How to find edges along calculated path in a navigation mesh

I have a navigation mesh consisting of triangles. I'm using the center of each triangle as a node for a pathfinding algorithm (A*). I would like to do path straightening with Simple Stupid Funnel ...
0
votes
1answer
42 views

Handling multiple agents in astar pathing

When working with grid based path finding in how do you normally handle different agent types? In the game I am working on I have a regular agent, and one that occupies 2 cells on the grid, and one ...
0
votes
0answers
23 views

D* lite optimized: what is wrong in my implementation of Search() function?

I'm trying to implement the D*-Lite pathfinding algorithm, as described in the 2002 article by Koenig and Likhachev for grid-based navgraph. But I stuck with problem. My ComputeShortestPath (in my ...
0
votes
0answers
91 views

How can I get a straight path using A*?

How to change A* work so that the path is more like a straight Euclidean distance? I read that you need to break some nodes, but how to implement this? I need heuristic like this: Is such a ...
0
votes
0answers
31 views

How to check in Unity whether tile B can be reached in a straight line from tile A?

I'm currently trying to smooth out my A* paths based on this article. This is what I want to achieve: But sadly I'm stuck at implementing the Walkable method. I ...
0
votes
0answers
27 views

How could I calculate the distance between the parent and neighbors node when there is a line of sight between two points?

I have completed my Astar algorithm in Python and now I need to convert it to a Theta star algorithm, I have built my line of sight algorithm below, but when I come to my Theta star algorithm I face ...
0
votes
0answers
122 views

Theta Star algorithm with line of sight

I have finished my A star algorithm and I need to add the work of Theta star to it, but I need to call the line of sight algorithm. I'm working on path planning for a UAV and I have created a grid in ...
0
votes
2answers
80 views

How to connect nodes in a star pathfinding for platformer games?

In this thread, it tells that in 2d platformer games, I should pre-define and connect node to find the correct path. But I don't understand how to find the node's children. In my program, I define ...
0
votes
0answers
35 views

Jump Point Search on an infinite grid

I recently found Jump Point Search and it seems like a really interesting algorithm. But I wonder about what its performance is like when your grid is of infinite size. When searching diagonally, is ...
0
votes
1answer
42 views

NavMesh - LoS and “Containing”

For a gameserver/backend, I have a navmesh for "walkable" areas in form of points/triangles. Now I want to check every gametick if the client is still in a legit place and if he shots/casts a spell, ...
0
votes
0answers
58 views

What are pixel-based path finding algorithms? (path doesn't need to be shortest)

I have a canvas of size of approximately 1000x1000 pixels. I also have a matrix that represents that canvas and returns -1 if that 'pixel' is walk-able. I need to find a path between one of my objects ...
0
votes
0answers
43 views

Unity Waypoint system

I am trying to code a way to choose between multiple paths using the waypoint system. I tried it with if statements but it was just very inefficient. Can anyone suggest me some ways to get this done? ...
0
votes
0answers
45 views

How to do pathfinding with rectangular agents

I am making a wargame like the old Warhammer fantasy battles or kings of war. These games focus on the movement of large rectangular units on a continuous map rather than a grid. Units can only move ...
0
votes
0answers
314 views

how to make AI do jump on navigation mesh system?

hi :D i'm currently using unreal for make a sand-box game for learning purpose. and due to the unique attribute of sand-box game, i am looking for how AI move naturally on map (which changes so often)...