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)

2
votes
1answer
278 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
284 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
865 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
144 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
269 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
216 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
774 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
1answer
449 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
263 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
120 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
360 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
319 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
307 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
196 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
573 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
2answers
112 views

How can I keep AI from getting stuck on each other?

I'm currently working on AI and, as stated above, I'm having trouble figuring out how to keep the AI from getting stuck on each other. More specifically, I'm working on two different behaviors for ...
2
votes
2answers
264 views

Basic Node Based Pathfinding

I am new to pathfinding but i have read and watched through some articles, blogs and videos about Pathfinding. Since those that i have read and watched from are mainly for RTS Games, Grid Based ...
2
votes
1answer
186 views

Pathfinding with car steering

Is there pathfinding algorithm which takes car steering into account? I have large space where user can place cars (trucks actually) and other blocker objects. Objects can be placed vertically or ...
2
votes
2answers
784 views

Using A*Pathfinding on terrain created by scripts?

I'm looking to use A* Path-finding as a method of navigating my game terrain. Trouble is, my terrain is built upon play using a script and A* grid does not detect this, therefore marking all nodes as ...
2
votes
1answer
44 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
113 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
624 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
2k 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
558 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
234 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
360 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
315 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
1answer
190 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
151 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
130 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
140 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 ...
1
vote
3answers
439 views

Why can't my A* implementation find a path out of an open room?

I tried to follow this article with the following example, but in my attempts it always ends up with a dead end. If we take G being 10 in a straight line or 14 in a diagonal, and H the distance in ...
1
vote
3answers
983 views

Would A* or Dijkstra be more proper for a grid-based tactics game?

In a grid-based tactical game (think Fire Emblem), would A* or Dijkstra be more proper for finding a path to use for enemy AI to determine the best place to move? A* has a better performance that ...
1
vote
2answers
242 views

What are some techniques used for mouse tracking, with a bit of “emulated lag”?

I am trying to implement a system, where the cursor (in my case the player's avatar) is always about 1.5 seconds (a configurable interval) behind where the mouse actually is. If I change the cursor's ...
1
vote
2answers
863 views

A* only for horizontal / vertical movement

anyone can share a link for a tutorial or article about optimizing A* for horizontal / vertical movement (no diagonal). Is not as easy as change the G values to 10 everytime. Thanks
1
vote
2answers
788 views

A* path finding for road network - data structure to represent directivity

I have been reading A* path finding to apply on a road like network structure. Most of the code I saw is about A* on tile based maps. There is a short description at Amit's page here about what I am ...
1
vote
2answers
580 views

Influence Maps for Pathfinding?

I'm taking the plunge and am getting into game dev, it's been going well but I've got stuck on a problem. I have a maze that is 100x100 with 0,1 to indicate if its a path or a wall. Within the maze ...
1
vote
2answers
1k views

How to make a gui button follow a path after a touch?

I would like a button in my gui menu to follow a specific path if we selected it, I am wondering how I could do it: if we touch the button, then it can only move on the specific path, it is an arc ...
1
vote
2answers
583 views

Moving an object around the the circle to the specific location in circumference

Well I have run out of ideas how to approach this particular problem.See the picture below: So the idea is that the object (dot in black) has to get to a point mark X (red X mark).However the ...
1
vote
1answer
307 views

How can I change the path a sprite is following in real time?

Is there a common way to implement a character following path that is issued and replaced in real time? For example: the character follows a path issued, and while it's on that path, if a new path is ...
1
vote
2answers
144 views

Algorithm for waypoint path following?

I have a worldmap, with different cities on it. The player can choose a city from a menu, or click on an available cities on the world map, and the toon should walk over there. I want him to follow ...
1
vote
2answers
921 views

Displaying possible movement tiles

What's the fastest way to highlight all possible movement tiles for a player on a square grid? Players can only move up, down, left, right. Tiles can cost more than one movement, multiple levels are ...
1
vote
1answer
177 views

Path-finding with obstacles that can be destroyed

There are several buildings on the map with size n * n, and a lot of tiles of obstacles that can be destroyed. Suppose I put one soldier on (x,y) of the map, the soldier can reach a building by ...
1
vote
1answer
120 views

How do I avoid obstacles on a predefined path?

I want is a character to walk along a path defined as a waypoint sequence. For example, a soldier patrolling around a castle. However, I want the soldier to avoid (dynamic) obstacles, without ...
1
vote
1answer
1k views

A star algorithm implementation problems

I’m having some trouble implementing the A* algorithm in a 2D tile based game. The problem is basically that the algorithm gets stuck when something gets in its direct way (e.g. walls) Note that it ...
1
vote
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 ...
1
vote
1answer
75 views

Pathfinding across mutliple levels

For a final school project, I have implemented an A* algorithm for pathfinding across a tile graph. So far, it has worked far surpassing my expectations. However now I'm in the process of adding a bit ...
1
vote
2answers
760 views

How should I store edge weights for my A* graph?

I am working on A* pathfinding in Unity, using C#. I am implementing Dijkstra's shortest path algorithm. I have a Dictionary with nodes as keys and corresponding lists of adjacent neighbors as values, ...