Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [path-finding]

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

0
votes
0answers
19 views

What course work or career path to choose in game development? [on hold]

I am a Bachelor's in CS drop out, I have a diploma in Game development from Asian Institute, I have been inactive for 6-9years now. But i am updated in the field of gaming, programming and development ...
0
votes
0answers
22 views

Good game engines that you can do 2d navmeshes [closed]

I'm making a turnbased tactics game that involves units moving on continuous maps rather than a grid map. Are there any good engines or tools for engines for making 2d navmeshes?
0
votes
1answer
48 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
69 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
79 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
31 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
36 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
24 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
80 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
43 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
67 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
50 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
69 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
67 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
106 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
69 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 ...
4
votes
3answers
125 views

RTS Unit AI: When to let the unit stop (due to local avoidence)

I am developing an RTS-like game, that have units that move and attack. I implemented path-finding and local-avoidance. One problem is when multiple units being ordered to the exact same position, ...
0
votes
2answers
77 views

Pathfinding How to store data for big terrain size

I am trying to implement my own pathfinding solution in unity but cant figures out how to store data. Following is my grid class which stores height, length and neighbour tile of tile. ...
0
votes
1answer
32 views

Shortest path to a road

I have a road network and a vehicle that is current off the roads. I want to find the shortest path to any road. An obvious solution is to run a pathfinding algorithm between the current vehicle ...
0
votes
1answer
320 views

Unity NavMesh pathfinding using Job System

I'm trying to write a system where I can run each enemy's NavMesh pathfinding in parallel, using Job System. The problem I'm having is that I can't pass the NavMesh agent argument as it's a reference ...
1
vote
1answer
73 views

Pathfinding to Get In Attack Range with “Transparent” Tiles

Currently I'm using A* and a raycasting algorithm to determine the path an entity (Player) should take to get close enough to the enemy (Enemy). The player has an attack range (it's illustrated around ...
0
votes
1answer
112 views

Correct way of combining A* and funnel

I implemented a pathfinding algorithm like this: There is a mesh of triangles that defines the area the player can walk. An A* algorithm is used for finding a path from the start triangle to the end ...
5
votes
1answer
195 views

Pathfinding in Procedural cave generation

I'm learning THIS tutorial about procedural cave generation using cellular automata with Unity. I want to implement pathfinding on some enemies, so I need to make a quantization of the procedurally ...
1
vote
1answer
84 views

Enemies overlapping

I have a simple WebGL maze game and has problem with enemies overlapping when they are going to target position. Now i'm detecting there collisions, but dont know what to do with them when they are ...
1
vote
2answers
108 views

Performance in pathfinding/road calculation

I have a question about the most effective way to detect road connection in a tile based world. Some time ago I already asked for "How to improve performance for expensive functions in 2d city builder"...
0
votes
3answers
108 views

Chunked A* Pathfinding Issues

I've run into an issue with A* pathfinding in a chunked world. This is my current setup: The world is designed in Tiled and exported as a .json file. I wrote a little program that converts the .json ...
0
votes
1answer
97 views

Generating nav meshes from tile based map (2D)

I'm working on a pathfinder for a MMORPG game, it's not mine; I'm RE it, now I need to create a pathfinder for monsters. But I figured that the client uses tiles for it's pathfinder (for players). ...
2
votes
1answer
27 views

Get the XZ to the right of a rotated point?

I need to do this entirely with math, take a look at this picture: What I'm doing is building a path finder algorithm that basically looks 30 units ahead, raycasts a few times perpendicular to the ...
1
vote
1answer
98 views

Looking for a square-to-hex pixel coords algorithm

So as the headline suggests, I am looking for an algorithm/algorithms used for square-to-hex and hex-to-square pixel coordinates convertion. I have an image which looks kinda "interpolated", meaning ...
3
votes
2answers
394 views

How can I maneuver an AI pirate ship for a sea battle?

I'm trying to picture in my head what would be required to make an AI controlled enemy do the following in a top down pirate sailing game: Approach the player ship Bring player in line with port / ...
2
votes
1answer
128 views

Pathfinding, 2+ tiles wide

I recently started learning python and I'm working on a dungeon generator, using images for the rooms, hallways and junctions. Example of desired result. So far I managed to generate a X * Y map and ...
0
votes
1answer
124 views

Can you use A* to make a unit move nonspecifically?

A* is typically used to calculate the best way to move towards something, and it's quite flexible when it comes to threats, extra movement costs, and 'refuelling' on the way to something. However, if ...
6
votes
2answers
600 views

RTS pathfinding

I'm doing my first RTS game (something like WarCraft 2) in own game engine using Monogame for graphics. I am wondering how can I implement pathfinding for a selected group of units. Movement is tile-...
0
votes
0answers
43 views

AStar Scores Explain Question. What is GScore?

I Tried to create AStar Algorithm and i'm already finished but i didnte work cause of this line : ...
0
votes
1answer
74 views

FixedUpdate is Being Called Less and Less Over Time…Why?

My game is still in the very early stages, but basically I have an enemy that follows the player if it can see them and will continue to follow the player for a few seconds after the player leaves its ...
1
vote
0answers
307 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 ...
0
votes
0answers
393 views

Is Godot's NavMesh viable for dynamic pathfinding (e.g. avoiding moving enemies)?

I am a novice (read: low-budget) designer looking at moving from Pygame to a real engine, and between Unity and Godot it looks like the latter has a much better 2D engine [1, 2, 3]. I would be happy ...
1
vote
1answer
76 views

Potential Field Pathfinding in a non Axis Aligned World

I am trying to create a game that has player created obstacles which can be placed anywhere in free space, and which has a large amount of enemy agents. In persuit of maximizing the number of agents I ...
2
votes
1answer
701 views

How to make ghosts AI chase Pac-Man in Java

I'm beginner at Java and I want to make ghosts chase Pac-Man in game. I read some algorithm like A* or Dijkstra but I don't know how to implement them in my game. Please help me.
1
vote
0answers
126 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
2answers
73 views

How do i retrieve individual Tile Information from a tilebased procedural World fast?

I am concerned about performance with my current setup; as I want to expand on it i need to figure out if I might need to change it. Current Setup: The Game/Prototype is similar to Dwarf Fortress or ...
2
votes
1answer
111 views

How to implement the graph for pathfinding using A*

The game I am working on is based on a maze where each level is procedurally generated. The pathfinding grid is a 2D array where each node holds its connections. Path requests are handled one at a ...
3
votes
2answers
91 views

2D Top Down: Can't follow the path accurately

In my game, there are many agents. Agents request a path, then after attaining a path to "goal" they follow the path. However player and many other things in the world can impact their position by ...
2
votes
2answers
58 views

Determining connectedness of rectangles

I am working on some functions to use in my enemy state machines. I want to write a function which determines whether the platform the enemy is standing on is connected to the platform the player is ...
7
votes
2answers
589 views

Game AI move towards player while avoiding an obstacle

I'm trying to move enemy towards player, while enemy also tries to avoid an obstacle if it's in its path. Here's a simple illustration of what I want to do: What I've tried: Making circular ...
8
votes
1answer
170 views

A* implementation issue

I admit defeat, I must ask the community the same question it has been asked a million times before: "What is wrong with MY implementation of the A* algorithm?" I am getting some very wonky results, ...
4
votes
1answer
68 views

Navigate multiple Units on a grid through a tight space with different directions

I just started learning about pathfinding algorithms. Assume we have this scenario: Blue and Green can move only on those tiles. They can also talk to each other. Blue wants to go through the tunnel ...