# Questions tagged [path-finding]

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

74 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
844 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 ...
193 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 ...
53 views

### Flowfield pathfinding behind obstacles on symmetrical grid

I use Fast iterative method to create my flow field. However when an obstacle is on the same axis as the destination, the vectors behind the obstacle point directly to the destination and ignore the ...
63 views

### Navigating an AI that shouldn't take the shortest path but the scenic route instead (e.g. fish)

I'm working on a sidescrolling game with an underwater "fish-like" AI that has some goals (interacting at various locations) and things to avoid (player). Started of with a Navmesh and ...
87 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 ...
1k 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 ...
120 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 ...
116 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++ ...
19 views

### Line of Sight/Clear Path Check Theta* For Rectangle Character

I am implementing Theta* pathfinding in a tile-based 2D game. A tile is either blocked or unblocked. The character has a rectangle collider with a width and height in tiles. Is there an algorithm for ...
227 views

### How to make pathfinding agents avoid each other using A* in unity?

So far Ive implemented a 2D grid graph using 2D physics. My enemies have a seeker script, AI destination setter (with the player position attached) and a basic AIPath script that is set to 2D When I ...
46 views

### Reducing the number of edges in a pathfinder

I've worked out an algorithm for pathfinding in a quite free-form terrain (not constrained to grids), with the limitation that it doesn't allow the moving character to rotate. I'll use it for AABBs so ...
59 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 ...
47 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 ...
109 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 ...
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. ...
256 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 ...
26 views

### Path following with turning radius and obstacle avoidance

I would like to move an object through a path found by A* star but taking into account the object's turn radius and movement speed, while also avoiding possible obstacles during a curve. After some ...
60 views

### Given a 2D array, how do I generate a random path of fixed length from a random point at length 0 to a random point at max length?

I'm trying to generate a random path on a 2D grid given that: The width and height of the grid are given The length of the path to generate is given The path can't move "back" The path ...
27 views

### How to adjust a path to avoid collisions with moving obstacles inside a nav mesh?

I'm writing a script for a bot and I'm a little bit stuck. There's a game, there's a player (me) and I want to get from point A to point B. I can find the path via bot's API (it returns a ...
61 views

### A* heuristic for a map that can have roads

I have a 2D grid which I am performing A* pathfinding on. Nodes are connected via a value of 3 in most cases (some connections are more expensive). In some (depends on the gameplay) circumstances the ...
42 views

### Any good pathfinding algorithm for lots of different speed zones? NavMesh seems not work

I have a terrain map with lots of different areas: roads, grass, swamp, forest, mountains. Each has different speed for the player. The map is continuous 3D map, not grids. Given a start & end ...
71 views

### How does heavily constrained delaunay triangulation work?

In short: I'm trying to find an algorithm for performing a Delaunay triangulation of a heavily constrained polygon (for the purpose of pathfinding), with the understanding that most of the resulting ...
21 views

### A* Pathfinding issues, player node is always off

so I am using Sebastian Lague's second video on A* pathfinding (https://www.youtube.com/watch?v=nhiFx28e7JY&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW&index=2), and since he is using a 3d model, ...
188 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 ...
75 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 ...
58 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. ...
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 ...
15 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 ...
35 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:...
703 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 ...
181 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, ...
300 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/...
139 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....
190 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 ...
371 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 ...
355 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 ...
314 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, ...
305 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 ...
308 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 ...
134 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 ...
46 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 ...
103 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 ...
845 views

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 ...
29 views

### How to assign an index to different node clusters? (for pathfinding)

Hellow~ So for a bit of context: i'm currently working on a RTS (way above may league) which already has a level editor and a node grid which maps the terrain, i previously make a navigation system ...
33 views

### “Blind” PathFinding for fleeing agent

I know there are plenty of algorithms for finding a path from A to B. There's also a good few articles on how to avoid an enemy in a 2D space. I can't find anything on escaping from an enemy in a ...
24 views

### Unit navigation and avoidance in an AutoBattler like game

I am not using an Engine (this is for an authoritative server in Golang). I've tried going with the flocking approach but got wonky and horrible movement. Looked into A* and into dijkstra, but cannot ...
25 views

### How to build path to cover for bot if cover moves while player moves?

I'm changing cover positions depending of player position (to keep obstacle between player and cover point). But when my bot using pathfinding algorithms to build path to that cover, he will spend ...
19 views

### How do I define my pool of Actions in such a way that they depend on variables in GOAP?

I'm attempting to implement GOAP in my game. The game is a simulation-type game that would not only benefit from GOAP, but is almost essentially a requirement based on the scope of what an agent can ...