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
5answers
1k views

Pathfinding in multi goal, multi agent environment

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o). . . . a o . . . . . . . o . g . . a . . . . . . . . . . o . . . . o o ...
3
votes
2answers
676 views

Multi-tile agent path-finding algorithm?

Suppose we have a uniform rectanglular grid as shown below. The a is an agent, o is obstacle and g is goal. What are the options of handling multitile agents (e.g. dragons or tanks)? . . . . o . ...
3
votes
1answer
154 views

Coordinate based travel through multi-line path over elapsed time

I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because ...
3
votes
1answer
617 views

Sample Projects/Source for Navigational Meshes

Anyone aware of any sample source code that contain Navigational Meshes? I'm aware of recast navigation (which is a little bit too complicated). - Written in C++. Preferably C# but C++ is ok.
2
votes
2answers
2k views

How can I better implement A star algorithm with a very large set of nodes?

I'm making a game with nodejs in which many enemies must converge on the player as the player moves around a relatively open space (right now it is an open field with few obstacles, but eventually ...
2
votes
1answer
109 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
3answers
292 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
4answers
244 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
2answers
144 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
1answer
160 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
3answers
424 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
3answers
285 views

A star pathfinding and discrete/smooth positions

The A* (A-star) algorithm usually represents a path on a grid. Once a path has been found, however, the path looks blocky and is not suited if you move your units with floating point datatypes. Here ...
2
votes
3answers
963 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
126 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
136 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
342 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
2answers
994 views

Path finding in grid for objects that occupy more than one tile

In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
2
votes
1answer
388 views

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

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
1answer
81 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
191 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
211 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
253 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
594 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
140 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
221 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
164 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
663 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
2answers
860 views

Pointy top hexagonal A* pathfinding

I'm trying to create a game with a hex based map with the points at the top. I have most of it working, however the path finding is being a little awkward. The heuristic I'm using is called euclidian ...
2
votes
1answer
407 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
2answers
296 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
231 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
271 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
172 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
496 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
1answer
993 views

Enemy Movement AI

I have a non-tile-based top down shooter game, and I have enemies set up. However I need the enemies to move to the player. Pathfinding algorithms will mean the enemies will just hug the wall. The map ...
2
votes
2answers
907 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
917 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
38 views

Moving unit along a computed path

I am generating a path using pathfinding.js. This returns a path of node coordinates from a matrix. Example: var matrix = [[0,0,0,0], //0 are passable, 1 are obstacles [0,1,1,0], ...
2
votes
2answers
84 views

How can I test if a point is behind a polygon in 2D?

In order to improve the performance of my visibility graph generator I am trying to figure out the following. Given the image below; is there a way to find out if a point is 'behind' the polygon? For ...
2
votes
1answer
400 views

Seek Steering Behavior with Target Direction for Group of Fighters

I am implementing steering algorithms with group management for spaceships (fighters). I select a leader and assign the target positions for the other spaceships based on the target position of the ...
2
votes
2answers
1k views

pathFinding performance in Unity3d

I am making Sniper game in unity 3d. In this game zombies will come randomly towards the sniper and sniper have to kill them. I am using RAIN(indie) for path finding. It works best when zombies are ...
2
votes
1answer
358 views

Dynamic obstacles avoidance in navigation mesh system

I've built my path finding system with unreal engine, somehow the path finding part works just fine while i can't find a proper way to solve dynamic obstacles avoidance problem. My characters are ...
2
votes
1answer
171 views

Is finding graph minors without single node pinch points possible?

Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up ...
2
votes
2answers
316 views

jQuery game - collisions

Please take a look at the picture below: It is and attempt in creating a "game" only with the DOM and jQuery. The blue boxes are "obstacles" and the user can move his pointer (not drawn in screen ...
2
votes
1answer
296 views

Dynamically creating astar node map by triangular polygonal map

My game's map format uses a bunch of triangles to make up the platforms and terrain in 2d. Right now I can set up a 2d array of nodes for the astar algorithm that basically is a bunch of rectangles ...
2
votes
0answers
62 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 ...
2
votes
1answer
149 views

Detect obstacles in path on a tile-based map

I'm creating a 2d game with a tile-based map, but smooth movement. I currently use A* in combination with some other tricks for pathfinding, and one issue what I've been dealing with is getting the ...
2
votes
0answers
125 views

Simulating crowds of enemies [closed]

I am wondering what would be a good way to handle enemy crowds generation and simulation. For example in a hack'n'slash game, how would one go about placing enemies and managing their movement in the ...
2
votes
0answers
89 views

Astar optimalization (A*) [closed]

So I have written own implementation of AStar (A*) algorithm to find paths around my 2d tile based map. My problem is that if I call it each frame (I need to do it) and I'm searching path from corner ...
2
votes
0answers
114 views

Design Question, Thoughts on Path Finding for a Galaxy Map [closed]

I am thinking through solutions for a galaxy map. We have different solar systems that need to be connected. I do think a-star (A*) is possibly a good solution but was curious if it was really the ...