We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [path-finding]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
38 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
45 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. ...
0
votes
0answers
21 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 ...
1
vote
0answers
19 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 ...
0
votes
1answer
55 views

Higher order splines for use with pathfinding

In this page, Amit explains that splines can be used to achieve movement on a found path. In the picture below, he explains that: The blue paths use splines, with dark blue being low order ...
0
votes
0answers
85 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
24 views

Which algorithm for controlling cars on a race track? [duplicate]

I think A* is a good place to start, but since cars cannot move in all directions (they move like cars do, trying to move forward and steer), I was wondering if someone could point me at other ...
4
votes
3answers
555 views

How to fix cutting corner problem in A-star pathfinding

So this is a problem when doing diagonal jumps (checking diagonal neighbor nodes). In 2d it can be prevented by doing some checks, like if up and right is blocked, don't take up-right neighbor for ...
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 ...
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
1answer
48 views

Unity Raycast not detecting layers

I am having problems with layers detection using raycasts. Context: I created a grid to use in a pathfinding algorithm on a 2D plane. I want to implement now different weights according to the layer ...
4
votes
1answer
188 views

Why is my A* algorithm is not taking future obstacles into consideration?

I am fairly new to programming, unity, and game design in general. I am following an old A* unity tutorial by Sebastian Lang and the algorithm he used doesn't seem to be completely accurate in terms ...
0
votes
0answers
49 views

Modifying A* pathfinding based on size of moving object [duplicate]

I've implemented basic A* pathfinding in my top-down 2D game, and I'm almost ready to test it, but I thought of something while adding the movement code to my enemies that I think could affect the ...
1
vote
1answer
59 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 ...
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 ...
20
votes
3answers
6k views

Efficiently pathfinding many flocking enemies around obstacles

I'm working on trying to improve the pathfinding for my game's enemies. Right now, they basically just constantly move towards the player's exact position by calculating the angle between themselves ...
0
votes
0answers
95 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
1answer
81 views

Infinite Loop in AStar (A*) Algorithm

Alright, so I've run into a problem where when trying to find a path that you cannot reach because it is blocked, it will continually loop and loop and loop (the 'open' list is ALWAYS filled). I ...
0
votes
2answers
60 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
1answer
37 views

Optimum Path Finding in Varied Terrain

I'm building a sort of city building sim and would like the ability for people to automatically place roads (or rail) based on a start and end point and for the sim to calculate the optimal route. I ...
0
votes
2answers
46 views

Pathfinding with direction considerations

Consider the following road network. The car (orange) needs to get to the red circle. It drives on the right hand side of the road and is initially facing down. The shortest path is the blue one. But ...
2
votes
1answer
83 views

How to stop switching between paths to a moving target?

I've noticed after implementing A* pathfinding into my game, that there is exploitable/unrealistic behavior that goes on when the player moves between two nodes that alter the path of the AI trying to ...
0
votes
0answers
34 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
41 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
2answers
94 views

A* GetNearest() implementation

I'm trying to implement pathfinding in my platformer and I'm having trouble coming up with a way to find the nearest node to a world point. I tried this: ...
1
vote
1answer
73 views

An algorithm to make one object follow another on a 2D grid

I am using Greenfoot, but this can apply to pretty much any 2D engine. So my question is a basic one that I somehow couldn't find an answer to already. Basically, if I have an enemy and the player, ...
-1
votes
2answers
258 views

Sebastian Lague's A* star pathfinding “On condition”

As the title suggests I have been following the wonderful series of tutorials dealing with pathfinding made by Sebastian Lague. My problem is that the code is meant to be working immediately after ...
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:...
3
votes
1answer
147 views

Dodge different type of obstacles

I'm writing a 2D game where the player has to kill a Ninja. This Ninja is coming closer with a constant speed chasing the player. The Map has some static obstacles like stones no one can pass. The ...
2
votes
2answers
81 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 ...
1
vote
1answer
267 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 ...
0
votes
0answers
45 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 ...
3
votes
0answers
64 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 ...
1
vote
1answer
81 views

How can I divide a grid map into clusters for path finding algorithm?

I am trying to implement HPA algorithm for finding the shortest path between two point. I came across the paper Near Optimal Path Finding Algorithm (by Botea, Müller & Schaeffer) but I am stuck at ...
1
vote
1answer
83 views

Finding a path with minimal number of turns on a grid?

There is a path, generated by my implementation of A*, where diagonals aren't allowed, and the heuristics is the Manhattan distance. Is there a way to always or nearly always find a path with the ...
1
vote
1answer
228 views

Godot: How do I asign movement cost to tiles in a Tilemap?

Pathfinding I am trying to apply godot's Navigation to create a pahtfinding enemy in a Platformer game. I've read about a method to allow for pathfinding to take into account gravity. My issue is ...
1
vote
2answers
54 views

Even tiles wide pathfinding on square based tilemaps?

By editing my A* algorithm as such that: a tile is valid if all of its neighbours are valid (checking this N-1 deep) I can find N wide paths, where N is odd, and my unit just follow the "center" ...
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. ...
0
votes
0answers
35 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
2answers
311 views

How to generate a random path on a 2d Grid

I want to create a random path in a 2d grid given a start point at the bottom row and an end point at the top of the row. I do not want the shortest path, or even the longest. Instead, I want a random ...
1
vote
1answer
327 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 ...
3
votes
1answer
138 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 ...
1
vote
1answer
125 views

A* heuristic for use with Goal Oriented Action Planner

Many of the high-level descriptions I've found for GOAP and similar planners suggest using A* for their path-finding, but I'm struggling to implement it for my own planner. Specifically, I'm ...
0
votes
0answers
42 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
16 views

Simple Automation of Car Path Finding Between 2 Points [duplicate]

I would think that it would be simple to have a car drive from A to B, but apparently I haven't been able to figure it out. My goal is to have a car begin at a certain position and angle, calculate ...
1
vote
1answer
43 views

Is there a way to automatically group tiles in a A* pathfinding grid to find the largest areas?

I'm making an RTS game using html canvas. I've made a program that randomly generates levels in order to test my pathfinding script. it divides the pathable blocks into squares so that you can apply A*...
1
vote
0answers
101 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
1answer
144 views

A* Pathfinding Finding One of Many Goals

I have my A* pathfinding algorithm right now working such that given a graph it can find the route from one starting node to one goal node. This works well for many problems, but sometimes I find ...
0
votes
0answers
226 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)...
1
vote
2answers
184 views

Recursively calculate possible pathway on a grid depending on max walk distance

I have a character that is placed on a grid. It has a variable maximum walking distance. Grid fields can be walkable or not walkable. As the character may has to walk around certain not walkable ...