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
0
votes
0answers
11 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
43 views

3D A* Pathfinding Algorithm Help

I want to make a 2D turn-based-strategy board game, so I'll need to give my game some pathfinding logic so that units know how to move from place to place. However, I want my levels to have multiple ...
1
vote
1answer
21 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 ...
0
votes
1answer
26 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 ...
1
vote
0answers
13 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
44 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
51 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
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 ...
0
votes
1answer
60 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
90 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
589 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
68 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
192 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
51 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
60 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
109 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
85 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
66 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
38 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
48 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
92 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
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
2answers
96 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
88 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
272 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
152 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
82 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
325 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
50 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
90 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
90 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
284 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
37 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
342 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
381 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
148 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
131 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 ...