All Questions
Tagged with astar or path-finding
739 questions
1
vote
3
answers
267
views
Enemy movement system on a 2D grid (Zelda-like)
I’m trying to implement a top-down Zelda-like enemy movement system. Consider a screen of x tiles wide by y tiles tall, each tile being 16x16 pixels.
I’m not asking for code here. I’m asking for ...
- 121
0
votes
0
answers
76
views
Is there a string-pulling algorithm that works directly with (3D) portals without checking LOS?
I'm working on a project where audio propagates through a series of rooms and portals. This is modeled by finding all paths from a source to listener and then merging their contributions into a final ...
- 1,031
0
votes
1
answer
148
views
Modular Pathfinding Between Connections
I'm creating a puzzle for my game, where you have to arrange pipes to transmit an electrical flow from one point to the other. Each pipe center contains a connector hub and each end contains the ...
- 13
0
votes
0
answers
45
views
Trouble aligning A* project dimetric grid with Unity 2022 LTS isometrig tile grid
I'm trying to use the A* path-finding project by Aron Granberg (free version 4.2.17) to do path-finding on an isometric grid (32x16 pixels). I have the whole system functional, but can't for the life ...
- 131
2
votes
1
answer
200
views
How to adapt the Anya any-angle pathfinding algorithm to handle non-discrete start/target positions?
Recently, I have been investigating the Anya pathfinding algorithm.
Anya is an optimal any-angle pathfinding algorithm.
However, it works only with discrete points on the grid.
Here is an excerpt from ...
- 105
0
votes
0
answers
100
views
Understanding C# Tasks
I use a lot of path finding in my Monogame project which is taking a toll on the framerate, because in the worst case finding a path can take 200ms. So I looked into using Tasks to spread path finding ...
- 111
1
vote
1
answer
262
views
Is there a way to determine if a Nav Link Proxy is encountered while finding a path between two points in Unreal Engine?
Problem definition: I have an AI (zombie) that is destroying a special object to reach a specific location. The object is stored as a blackboard value and is a child actor of a NavLink(To trigger ...
- 21
0
votes
1
answer
562
views
How to make an enemy able to walk on walls in Unreal Engine?
I'm working on my 1st title called Infernal,
and I'd like to make the enemy able to walk on both ground and walls.
For exemple: let's say the enemy is running towards the player and he gets shot. ...
- 1
0
votes
0
answers
80
views
How to optimally transfer between nodes when each connection can only handle a certain number of things at a time?
Let's begin with a picture:
I am currently making a turn-based strategy game set in space where you can settle colonies and have to transfer minerals from the colonies ("foo", "bar&...
- 8,543
0
votes
0
answers
91
views
How can the A* algorithm revisit the same node twice in multi-agent pathfinding(MAPF)?
I am attempting to solve a MAPF-like problem using the Conflict-Based Search (CBS) algorithm. My specific problem is based on a grid graph where some edges are not connected.
For example, in the ...
0
votes
1
answer
81
views
path-finding question of 2d game server
I'm trying to create a game server. The game I want to create has a following feature.
2d (isometric view)
~300 users can play so a map will be not that small
all units can move in any angle (not ...
- 11
2
votes
2
answers
137
views
Improving local collision avoidance to navigate around large obstacles
For my collision system I’m using a boids-like method that works fine for "small" obstacles (like other characters) where the character can turn slightly left or right to avoid the obstacle ...
- 333
5
votes
5
answers
2k
views
Grid-based pathfinding for a lot of agents: how to implement "Tight-Following"?
Note: the main problem has nothing to do with the TYPE of pathfinding algorithm (A*, flow-field etc), allow me to explain:
I have a 2d grid and a lot of agents moving around, I want it so that ...
0
votes
1
answer
206
views
Setting up AI Pathing in Godot 4.3, NPC not moving but it is updating the pathing correctly
I am making a project in Godot 4.3 I am using a gridmap for the map and I have the NavMesh set up correctly, when I am in game I can get it to show me its pathing and it will update correctly ...
2
votes
1
answer
464
views
2D Pathfinding with rope constraint
I have a character linked by a rope to a fixed point, in an environment with obstacles.
I want to do a pathfind that take into account the rope.
Here, if the character followed my current pathfind in ...
- 51
1
vote
0
answers
124
views
Get a obstacle avoidance path base on a grid-based map and non-grid based movement
black line is grid-based path got from A* algorithm, and red one is smoothed path by use Funnel algorithm.
when B move through T or stop at T, it will overlap with A, My problem is how to get a path ...
- 11
2
votes
0
answers
101
views
How to make enemies navigate around each other in a grid-based game?
I am making a 2D top-down grid-based game where the movement is similar to older Pokémon games so it's locked to a grid. I implemented A* pathfinding for my enemies with a bool[,] that indicates ...
- 21
3
votes
3
answers
1k
views
Recreating StarCraft 2 pathfinding – no navmesh method seems fitting
As a hobby project I am trying to re-create pathfinding similar to StarCraft 2 based on the presentation from GDC 2011: https://www.gdcvault.com/play/1014514/AI-Navigation-It-s-Not
(Image source)
The ...
- 133
1
vote
2
answers
392
views
A*, what to do about duplicate items in the min-heap, if anything?
I'm trying to implement A*.
I'm storing the queue of nodes to visit in a min-heap, and I'm seeing the same node being added more than once to it (with different priority). Wikipedia's pseudocode ...
- 2,054
1
vote
1
answer
84
views
How do I get a Unity Job to update external data?
I'm relatively new to Unity, and I wanted to use the Job system for a complex pathfinding algorithm, since it will likely be used alongside multiple instances of NPCs attempting to find a valid route. ...
- 11
1
vote
1
answer
202
views
A-star algorithm after 2D tilemap 90-degree rotation
I am learing Unity and for now trying to implement a simply pathfinding alogorithm in a simply 2D isometric diamond-shaped tilemap.
Recently I learned a way how to rotate tilemap and I already have a ...
- 13
0
votes
1
answer
117
views
How to delete unnecessary points given a jointed path
I'm writing code for client-side pathfinding, the player can setup more than one point and then pathfinding in segments finally get a concatenated path.(actually it's for the long distance pathfinding,...
6
votes
4
answers
729
views
In a tile based game, with units that can move a specific amount per turn, how do i make my pathfinding avoid damage unless it is the only valid path?
i am making a 3d tactics game, visually similar to something like final fantasy tactics. it's tile based, with units able to move up and down the level onto buildings and up staircases and what have ...
- 65
0
votes
1
answer
104
views
I'm trying to find a way to iterate through a list of game objects to find furthest object in the list. Then re iterate if path is blocked
I've got the first part of the code working. It iterates and does a check through the gameobjects to find the furthest nav point to hit. Then it calculates path to see if its valid or not. Now I'm ...
0
votes
0
answers
112
views
Find the best attack position
I'm doing what this thread is doing except that it's not very satisfactory. What this does is finding the "closest" attacking position. But typically you want the attacker to attack from as ...
1
vote
1
answer
305
views
Funnel algorithm : not possible with all convex polygons?
Disclaimer : yes, the whole map is not convex. But all of its subdivisions are ! (And that's what matters)
Hi ! I got A* working with nav mesh. Now I need to find the tightest path along the mesh path....
0
votes
1
answer
154
views
Grid-Based pathfinding with object size. Avoid colliding into big-enough spaces
I already implemented a Grid-Based pathfinding algorithm and I works. I also updated it so it takes into account the objects size and ignores paths where the object wont fit. However, I ran into a ...
- 3
0
votes
2
answers
261
views
How to make ranged RTS units move to their firing range from an opponent using flow fields?
I am trying to make a simple real-time strategy game (only the battle system of units fighting each other; no building, no economy, only battles and victory). I am using flow fields to make the units ...
- 3
1
vote
1
answer
1k
views
Generate a fully 3D NavigationRegion/pathfinding in Godot 4
I'm making a spaceship game where the enemies and the player have the full 6 degrees of freedom, so can move forward/backwards, left/right, up/down and can also rotate in all three axes. I'm wanting ...
- 127
0
votes
0
answers
142
views
A* implementation does not work correctly
I'm trying to implement a 3D pathfinding system based on the A* algorithm. This tutorial served as the starting point for my implementation. I tried to remake it for pathfinding in three dimensions, ...
- 11
0
votes
1
answer
2k
views
CharacterBody3D gravity isn't working, and player won't touch the floor
I'm trying to create an isometric game with Diablo-like control, but gravity isn't working. The CharacterBody3D won't touch the floor, the print(is_on_floor()) always results false.
Here's my code for ...
1
vote
1
answer
2k
views
How to deal with large number of Navmesh Agents?
I have more than 200 units in a single scene, all of them use Unity's NavmeshAgent to set their destinations to the main target. The problem I'm facing is that some ...
- 99
0
votes
1
answer
110
views
A*Pathfinding generating wrong path
I'm building a maze game where there's an enemy ready to pursuit the player if the player gets in his range, I'm using A*Pathfinding algorithm to do so, and I build the maze in a procedural way, where ...
- 113
0
votes
2
answers
371
views
Weighting navigation mesh nodes for A*
I'm trying to implement path finding for my game using a navigation mesh and A* search. While I believe I got this working correctly I'm having trouble getting desired results because I don't know how ...
0
votes
3
answers
917
views
How to prevent the player from completely blocking the enemy paths in a tower defence game like Fieldrunners?
I am new to Unity and want to create a tower defence game like Fieldrunners.
I need help to create the grid placement area for the towers so that there is always a path for enemies to travel. I mean ...
- 3
1
vote
0
answers
204
views
What's the best way to store irregular areas of my map? (hierarchical pathfinding and grid segmentation)
This is for the development of a roguelike/management game.
I'm trying to implement HPA (hierarchical pathfinding with A*), and I've found a few good resources (suggestions appreciated) in the forms ...
- 43
0
votes
1
answer
158
views
AStar taking care of collisions for a rectangle
How can I explore a path with A* (or another) by taking care of a rectangle collision ?
I have a 2d map, where I know for each coordinate if it is an obstacle :
For example, dark tiles are not ...
- 159
0
votes
1
answer
300
views
Implementing a bot to find the player in a grid
I have a 2d array with ground represented by 0s and the walls represented by 1s.
Player can use a LOOK command or a MOVE command. Look command returns a 5x5 array centered around the player and the ...
0
votes
2
answers
775
views
Defining path for tower defense game
I'm currently developing a tower defense game as a part of a group project in school. This game will be programmed in C++ using SFML. We are having trouble with finding a good way to define the path ...
2
votes
1
answer
5k
views
Creating a nav mesh
I'm coding a custom engine using Python and Pygame. It's a top down 2D isometric RTS and I wan't to implement pathfinding for my units.
My research has lead me to using a Navigation mesh which seems ...
- 63
0
votes
0
answers
149
views
Connecting nodes for A* algorithm
I am currently working on implementing a pathfinding module for my 2D game engine that I am writing in Python using Pygame.
Currently there are objects such as trees or buildings which can be placed ...
- 63
0
votes
1
answer
855
views
Player overshoots path using NavigationAgent2D and NavigationPolygonInstance in Godot 3.5
I'm trying to add a click to move feature in my game using the new NavigationAgent2D and NavigationPolygonInstance but sometimes when the player reaches the end of the navigation path or changes ...
0
votes
1
answer
909
views
Making Multiple NavMesh agents go to different destinations in unity
I am trying to make an Rts game in unity and am trying to make it so that units can go to different destinations, I have a selection system that deactivates their Navmesh agents and the script that ...
10
votes
3
answers
4k
views
How can I shorten the length of time spent on finding a path using my A* pathfinding code?
I am working on a game where the player and enemies move between discreet tiles, with only orthagonal movement (like pokemon). The game also runs on a turn system, so the player makes a move input, ...
- 117
0
votes
0
answers
254
views
How do buildings in (Tile based) city builders/colony sims keep track of each other? [duplicate]
Like, how does a building in these games know if they're being powered? Or if they're within range of influence of a hospital or fire station, etc.
How would they know where to send an NPC or ...
1
vote
2
answers
260
views
Dynamically generating and modifying non-Euclidean/Tardis houses while maintaining AI navigability
General Description
I want to build a tech demo about a game concept I am carrying around for quite some time now. A lot of influences from different sources shaped this, and I will try to hint on its ...
- 111
10
votes
3
answers
3k
views
Maintaining unit formation while following path
I'm currently working on a 2D Age of Empires style RTS game.
Here's my problem:
I'm currently using the A* algorithm (via Path finding package) to move my units.
When you select a "group" of ...
- 101
2
votes
0
answers
487
views
What's the best strategy for incorporating jumps into a 3D AI navigation algorithm?
I'm trying to make a game centered around chase sequences in a 3D level with a high degree of verticality and movement options for the player. Basically think Breath of the Wild in an urban landscape ...
0
votes
1
answer
617
views
Pathfinding over network and local avoidance
I'm trying to build a little MOBA game (max 10 players) in Unity and i'm really stuck with the pathfinding / local avoidance.
Here is what i'm doing when user click to move on the map:
Client send a ...
- 309
0
votes
0
answers
201
views
Pathfinding sprite disappears when approaching the player in Unity
I'm trying to make AI for enemies in my game. I applied a pathfinding (A*) script to my enemy sprite, after which the sprite began to follow the player. But when the enemy approaches the player, the ...
- 1