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

learn more… | top users | synonyms (2)

3
votes
0answers
187 views

How to get NPC to Find and Follow Path to other NPC?

Problem: I am using Skyrim Creation Kit to create a very simple mod. I want the mod to make one NPC follow another NPC. My first problem is that I am not really 100% sure where to start. The second ...
3
votes
1answer
224 views

How to implement visibility graph pathfinding in Unity/C# to detect paths (i.e. visibility connections) efficiently?

I am struggling with implementing continuous path-finding trough visibility graphs. Notice, I know that grids can be used even when movement is not trough grids (e.g. Theta*). But for my current ...
3
votes
1answer
218 views

Local avoidance together with any-angle types of A* Pathfinding

Recently I have been implementing the Block A* any-angle path-finding algorithm in a project I have, for which I need extremely efficient results due to the large number of NPCs. However, I still do ...
3
votes
2answers
331 views

Aligning pathfinding to the center of tiles?

I'm looking to achieve tile by tile movement in a project I'm working on. I employed the use of the asset Simply A* Path-finding to allow a unit to navigate the terrain. Since the tiles are ...
3
votes
1answer
448 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS ...
3
votes
0answers
335 views

Pathfinding with portals? [closed]

I'm not making a game with portals in it (one way or bidirectional). These portals instantly teleport characters from one location to another. How would I implement pathfinding? Here's an animation ...
2
votes
4answers
575 views

Why is my A* Pathfinding incredibly slow?

I'm trying to use A* to make my enemies move about, but it takes up to 20 seconds to get a path to walk. My grid is only 64*64. This is my code: #include "AStar.h" #include "Node.h" #include ...
2
votes
1answer
153 views

How can I adapt A* pathfinding to work with platformers?

I have an A* implementation that works in "top down" situations where gravity is not taken into account for pathfinding. But, I am looking to modify to work in a 2d platformer situation. I am using ...
2
votes
1answer
115 views

Should pathfinder in A* hold closedSet and openedSet or each object should hold its sets?

I am about to implement A* pathfinding algorithm and I wonder how should I implement this - from the point of view of architecture. I have the pathfinder as a class - I think I will instantiate only ...
2
votes
2answers
120 views

How to convert non-discreate data for discreate pathfinding?

I have a list of entities that looks like [{x,y,width,height}, {x,y,width,height}, ...]. This list is non-discreate, It doesn't follow a grid. entities can be positioned at floats like x:2.345 Most ...
2
votes
2answers
176 views

Pathplanning A* Getting stuck in wall

I'm having a problem with my pathplanning. I can plan a path and make my character follow it, that's not a problem but then i plan a path around a wall it takes the shortest way as A* suggests, which ...
2
votes
3answers
634 views

Discovering path through unknown territory

Let's say all the AI knows about it's surroundings is a pixel-map that it has which clearly shows walkable terrain and obstacles. I want the AI to be able to traverse this terrain until it finds an ...
2
votes
3answers
478 views

Best way to implement mouse-based movement in MMOG

I want to design an MMO where players click the destination they want to walk to with their mouse and the character moves there, similar to Runescape in this manner. I think it should be easier than ...
2
votes
4answers
270 views

Path tables or real time searching for AI?

What is the more common practice in commercial games; path lookup tables or real time searches? I've read that in many games path lookup tables are pre-calculated and baked into each map, so to ...
2
votes
3answers
327 views

Smooth path/direct movement

I have a tile based isometric map and an A* algorithm that returns a path. I am looking to smooth this path efficiently but with good aesthetics. Basically i am using my grid for building the map and ...
2
votes
2answers
1k views

Javascript A* path finding

I am trying to learn A* path finding. I am using this library - https://github.com/qiao/PathFinding.js But there is one thing I don't understand how to do. To find a path from player.x/player.y ...
2
votes
1answer
185 views

Level design: compute minimum time between two items for player traversal

Do any game toolsets offer a means of computing the minimum time it would take a player to move between two objects (or positions, more generally) in a level? I'm not asking about how one would go ...
2
votes
2answers
132 views

Funnel algorithm

I'm implementing the funnel algorithm for pathfinding. After searching many resources I found those : https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf ...
2
votes
3answers
2k views

Map building - Tower Defense

Before diving too deep into my question, let it be known that I am learning as far as java script goes and figured a simple Tower Defense game would be an excellent way to learn things. So I have ...
2
votes
1answer
401 views

What tools are available for creating 3D collision and pathfinding data? [closed]

What is the process of creating geometry data to assist on NPCs movements and such on a 3D world to avoiding having them from going through the ground, etc? Are there specific modelling programs that ...
2
votes
2answers
185 views

A* pathfinding for grid with direction-dependent nodes?

I'm trying to understand if the A* algorithm is a possible pathfinding solution for my game. I have a simple grid of nodes that an enemy can move around on, but the nodes represent traversable ...
2
votes
1answer
219 views

Is it more efficient to use an A* algorithm or a line system drawn in pathfinding in C#?

I was recently introduced to the A* algorithm when I asked a friend about making AI/NPC's in video games move to certain points and it sounded very interesting. I am building an FPS and it has AI that ...
2
votes
1answer
142 views

How to determine where on a path my object will be at a given point in time?

I have map and an obj that is meant to move from start to end in X amount of time. The movements are all straight lines, as curves are beyond my ability at the moment. So I am trying to get the ...
2
votes
1answer
607 views

World-map navigation and path-finding

I'm designing a 2d RPG where you navigate on a overhead map. The terrain is mostly open with big parts of inaccessible terrain such as mountains and rivers. The player navigates short distances at a ...
2
votes
1answer
464 views

Pathfinding in a 2D “sidescrolling” strategy game

I've been thinking up a real-time strategy game that plays on a platformer type of map. The collidable portion of these maps will be made up of square tiles. I've done A* pathfinding in top down tile ...
2
votes
1answer
554 views

A* in 2D grid with obstacles in between graph nodes

I am using standard A* (and Jump Point Search) for pathfinding in my 2D game. A map in this game is a simple 2D grid (tile-based). A node (i.e. grid cell) in my map graph can either be blocked or ...
2
votes
2answers
281 views

How can I incorporate the path of a jump into my A* implementation?

I need to calculate the path of a jump via A* for a simple platformer game. Calculating the direction is simple, but translating the jump physics into pre-calcuted voxel paths is a bit difficult. ...
2
votes
1answer
339 views

how do I make an enemy target an ally unit?

I have 2 different classes, a EnemyFighter class, and a EnemyBomber class. both are planes that I have that can fly around the map.( i also have AllyFighter, and AllyBomber) So far they can follow ...
2
votes
3answers
299 views

In A star, what is the point of recalculating the best path?

In A* after the finding the next node with the lowest F value, you have to search the adjacent nodes again. When you find a node that was already in the open list, you're supposed to check if the g ...
2
votes
2answers
1k views

How to implement pathfinding in this situation

So I'm creating a game for android using the libgdx library. I render the map from a tmx file and in it all the water tiles have the property of blocked. My player(a sprite) moves to where I ...
2
votes
1answer
149 views

Pathfinding results in false path costs that are too high

I'm trying to implement pathfinding in a game I'm programming using this method. I'm implementing it with recursion but some of the values after the immediate circle of tiles around the player are ...
2
votes
1answer
307 views

How to predict future location of a Car in a Navigation Mesh based pathfinding system?

I am developing a car based shooting game in which the Cars have to shoot each other 3/4 times and eliminate it from the game. I am trying to develop the AI for my cars now. The problem is how can I ...
2
votes
1answer
2k views

Pathfinding with different sized units [duplicate]

I am actually working on a general purpose pathfinding library (find it here), mostly oriented for grid-based maps. I was looking for ways to integrate support for pathfinding with units of different ...
2
votes
1answer
262 views

Wander algorithm for a maze [duplicate]

I am making a multiplayer coop FPS game. I have created the first monster with it's AI. I have worked out the A* algorithm for the level based on the triangles of the walkable mesh. So I can already ...
2
votes
1answer
873 views

Pathfinding and BSP with Box2D

I'm looking into implementing AI in my 2D side-scrolling platformer, and I'm looking into using algorithms such as A*. For many kinds of pathfinding, we need some sort of grid or systems of nodes or ...
2
votes
3answers
886 views

Pathfinding for units of variable size

I'm using a grid map for a top-down RTS, and using a* for pathfinding. Specifically, I've found one implementation which is heavily optimised, and I've been using it for a while, but now I've realised ...
2
votes
1answer
459 views

All Pairs Shortest Paths in Weighted Undirected Graph

I'm currently working on path-finding for my game and need help with finding an efficient algorithm to calculating the all-pairs shortest paths in a weighted undirected graph (each vertex in the graph ...
2
votes
1answer
1k views

Pathfinding with MicroPather : costs calculations with sectors and portals

I'm considering using micropather to help me with pathfinding. I'm not using a discrete map : I'm working in 2d with sectors and portales. However, I'm just wondering what is the best way to compute ...
2
votes
1answer
381 views

Pathfinding and clusters

For an assignment, I am required to implement an A* algorithm in order to find the shortest path between two object using different heuristics null, this effectively becomes Dijkstra Euclidean ...
2
votes
2answers
185 views

How to find all the possible places to go on a grid?

Given the amount of steps you can take in a grid, how could I implement a way to get all the possible places a unit can go to, in a game like Advanced Wars? I have currently got A* path finding ...
2
votes
2answers
418 views

What's the best way to move cars along roads

I am implementing car movement game (sort-of like Locomotion). So 60 times a second I have to advance the movement of each car. The problem is I have to look ahead to see if there is a slower car, ...
2
votes
2answers
399 views

Prevent collisions between mobs/npcs/units piloted by computer AI : How to avoid mobile obstacles?

Lets says we have character a starting at point A and character b starting at point B. character a is headed to point B and character b is headed to point A. There are several simple ways to find the ...
2
votes
2answers
338 views

Pathfollowing with acceleration - centripetal force

I'm implementing A* waypoint pathfinding with some twists. One of the problems I'm encountering is because I do not change velocities of the agents directly but rather I do so through forces. Which ...
2
votes
2answers
209 views

Grouping units in world space

I figure that I intend to generate, for group orders, one optimal path, and then use a flocking algorithm to "glue" the units together as they all follow this one optimal path. However, a naive ...
2
votes
1answer
642 views

3D RTS pathfinding

I understand the A* algorithm, but I have some trouble doing it in 3D to suit the needs of my RTS Basically, in the game I'm making, there will be agents with different sizes of OBB collision boxes. ...
2
votes
2answers
1k views

Are there any usable performant path-finding libraries for python?

This is cross-posted from StackOverflow, please feel free to answer there too: I'm working on a real-time isometric RPG in python, and wish to target mobile devices as a platform. The main area where ...
2
votes
1answer
97 views

How can I remove unnecessary nodes from my path?

How do I remove the unnecessary nodes from the path to make it as short as possible? Idealy I'd like the result path to look like the green line. The red thingy is not walkable. var ...
2
votes
1answer
35 views

Add navigation obstacles during runtime lags

Please watch this short video. http://screencast.com/t/vw2a5FdOOT It shows the problem. It's using the build in Unity navigation and followed the guide to build the demo in the video. Everytime I ...
2
votes
1answer
62 views

Storing visibility graph for path-finding: do redundant and non-visible pairs of points have to be saved?

Using C# in Unity, I have recently implemented an algorithm that determines during run-time the visibility graph of a given scene in my game project (visibility between corners of obstacles). Now I am ...
2
votes
1answer
97 views

Where/how should A Star tie breaking occur?

I've recently written a path finding script that utilizes a basic implementation of the A Star algorithm. It works fine but is not very fast. This is due, at least in part, to the fact that it isn't ...