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
6
votes
2answers
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 ...
4
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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++ ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
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
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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, ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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. ...
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
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 ...
1
vote
0answers
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:...
1
vote
1answer
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 ...
1
vote
0answers
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, ...
1
vote
0answers
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/...
1
vote
0answers
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....
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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, ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
845 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
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
27 views

Converting 3D to 2D (A* pathfinding)

I am following Sebastian Lague's A* pathfinding series, and I am on the episode where he explains path smoothing: https://www.youtube.com/watch?v=NjQjl-ZBXoY&list=...
0
votes
0answers
60 views

Too many neighbors when pathfinding in Sparse Voxel Octree

Imagine we have upto 9 or so layers (that is depth), and due to some big colliding platform in the level, one of the empty nodes close to the root have all much smaller nodes as neighbors at one of ...