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
24 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
34 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 ...
2
votes
1answer
113 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 ...
-2
votes
0answers
21 views

A* Algorithm For Large Units [duplicate]

i used https://www.geeksforgeeks.org/a-search-algorithm/ to build my A* pathfinding in my game. I am now trying to add large units so basically units that take up multiple tiles
0
votes
0answers
47 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
45 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 ...
-1
votes
0answers
23 views

How could I match my line-of-sight with Theta star? How could I fix my below problem?

I'm trying to implement my Theta star algorithm, but first I need to implement the line-of-sight algorithm. I have implemented below my lineOFsight algorithm in Python, I don't know how accurate it is....
0
votes
0answers
36 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
75 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
56 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
39 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
68 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
31 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
32 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
91 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
54 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
227 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
139 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 ...
0
votes
2answers
62 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
162 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
38 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
59 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
68 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
77 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
164 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
53 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
23 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
32 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
244 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
235 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 ...
2
votes
1answer
120 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
115 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
41 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
42 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
90 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
116 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
180 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
147 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 ...
1
vote
1answer
62 views

Snake AI - Is a Hamiltonian approach valid for all grid sizes?

So, as has been done many times before, I am designing an AI that can play Snake as effectively as possible. It didn't take me long to find this extremely useful thread here: How to find a safe path ...
15
votes
4answers
6k views

A* Algorithm for Tactical RPGs?

I'm messing around with writing a really poor tactical RPG in C++. So far I have a 2D tile map and just got the A* algorithm working based on the pseudocode in the wikipedia. But real tactical RPGs ...
2
votes
1answer
153 views

Closest node in A* pathfinding

For my 2D Unity game, I've implemented A* pathfinding based on waypoints. System already handles building graph from waypoints on scene (which are manually placed objects), as well as finding and ...
0
votes
1answer
122 views

A* Quad/Oc Tree path-finding vs Navigation Mesh path-finding

Main What are the differences between those path-finding algorithms. Is Navigation Mesh faster in finding the path? Is it more correct than Quad/Oc Tree? Does Navigation Mesh use Quad/Oc tree under ...
3
votes
2answers
125 views

Pathfinding with non-deterministic transitions between nodes

Consider a map not unlike a board game, where some of the moves are made non-deterministic. For example, moving onto certain cells will require you to roll a dice to determine where you should move ...
0
votes
0answers
13 views

Pathfinding/Steering with limited rotation [duplicate]

I am looking for an algorithm to guide some ships in a turn based game. The trouble is they should have a limited rate of turn, and I want them to navigate them to both a target position and a target ...
0
votes
3answers
91 views

Can I speed up “potential fields” pathfinding when it's working on a large grid?

I'm looking to implement a pathfinding algorithm that will allow me to throw hundreds of spiders at the players in my grid-based game. I can implement this with A*, but I'm worried that that algorithm ...