# Tagged Questions

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

112 views

### Path finding to collect enough items before the fight with the enemy

So I have the following problem : a X by Y grid. On the grid there is a character and a monster and some items that give bonus points to the character's damage if picked and holes that must be avoided....
271 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 ...
399 views

### best way to implement movement after A* pathfinding? tile-based movement vs pixel-based?

I was able to implement the A* pathfinding algorithm to calculate a path from the enemy to player. After trying to do movement well, I realized I ran into all sorts of problems. I was able to add ...
47 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], ...
178 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 ...
146 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 ...
160 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 ...
257 views

### Pathfinding avoid a list of polygon

i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very ...
801 views

### “Line of sight” path across navigation mesh

I want to calculate the line of sight in a navigation mesh. Consider the image below, the yellow line is the result of only A* and the red line is the result of a line of sight" algorithm that uses ...
806 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 ...
630 views

### how to implement A Star path finding on 2D map with large tiles

The map tiles I have im my game are 64x64 pixels, and the characters are 16x16 pixels. I was reading about A Star path finding and I was wondering if I need my tiles closer to the size of my ...
379 views

### Square Grid Polygonal Terrain Query algorithm?

I have a square, fixed-grid terrain with one terrain type per grid unit in my game, and I want to do an arbitrary polygonal terrain query which returns all of the grid units enclosed/intersected by ...
152 views

### Finding the nearest object, considering obstacles

For the purposes of this question, we'll assume it involves a Janitor assigned to clean up trash in a building. Given that it is a building, it is safe to assume there are one or more rooms, walls, ...
165 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 ...
165 views

### How do I avoid A* pathfinding lists exploding? [closed]

I'm attempting to implement A* pathfinding in my game, and it works for most of the iterations I've tested it with, but I've hit a few random cases where it never stops loading items into the Closed ...
1k views

### Pathfinding in non tile-based 2d map (maybe potential field)

I am developing a top-down 2d zombie shooter in AS3. I have implemented collisions against segments (line from point a to point b), polygons (array of points, convex) and round obstacles (center and ...
148 views

### Implementing ClearPath (crowd pathfinding)

This is the academic article: http://gamma.cs.unc.edu/CA/ClearPath.pdf Here is the confusing part (marked in red): The first part is the path in which the object will move. The first part of ...
291 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. ...
3k views

### NavMeshAgent in Unity giving jerky performance

I am using NavMeshAgent in my Unity project to calculate and move my object to a particular location. When I do: navMeshAgent.destination = destinationPt the object starts moving, but the motion ...
982 views

### How can I make a character smoothly traverse a list of waypoints?

I want to set up paths for enemy characters in my game to patrol. I'd like to be able to define a list of waypoints and have the enemy follow the path from one point to another, but in a smooth curve. ...
376 views

### How can I compute the shortest path in Euclidean environments with non-convex polygons?

Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles?
294 views

### Pathfinding Search for Path of Specific Length

I am creating a roguelike. This question applies to random map generation. First, I generate areas using a BSP algorithm, where I randomly divide the map into areas. Then, I generate a graph of the ...
123 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 ...
274 views

### How can I test if an object will “fit” during pathfinding?

I'm tinkering around with a 2d game where obstacles are polygons of arbitrary shapes, sizes and locations, and movable entities (players/enemies) can also be of arbitrary sizes. What's a good general ...
2k views

### How does the Simple Stupid Funnel Algorithm work?

Working with the funneling algorithm shown on Digesting Duck I'm not sure how the detection of the funnel works. Can someone explain the method clearly to me or suggest an alternative way of ...
587 views

### How can I plot a radius of all reachable points with pathfinding for a Mob?

I am designing a tactical turn based game. The maps are 2d, but do have varying level-layers and blocking objects/terrain. I'm looking for an algorithm for pathfinding which will allow me to show an ...
829 views

### Implementing David Silver's Cooperative Pathfinding in Real-Time

I'm currently implementing David Silver's Cooperative Pathfinding algorithm for a 2D game with grid-based movement (all eight directions). The issue I'm having trouble wrapping my mind around is the ...
201 views

### How to proceed on the waypoint path?

I'm using Dijkstra algorithm to find shortest path and I'm drawing this path on the screen. As the character object moves on, path updates itself(shortens as the object approaches the target and gets ...
612 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 ...
322 views

### How to optimize my A* algorithm

I'm working on a roguelike, and I think my A* algorithm is insufficient. My general algorithm for building the dungeon is: Place rooms Figure out which rooms should connect by a relative ...
266 views

### Overlaying grid for pathfinding

I have a simple problem. My game is not grid-based, so units can be at any arbitrary coordinate and move at different speeds. My obstacles are all rectangular and axis-aligned, so naturally it makes ...
1k views

### How to make natural-looking paths with A* on a grid?

I've been reading this: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html But there are some things I don't understand, for example the article says to use something like this for ...
702 views

### A*, Tile costs and heuristic; How to approach

I'm doing exercises in tile games and AI to improve my programming. I've written a highly unoptimised pathfinder that does the trick and a simple tile class. The first problem i ran into was that the ...
1k 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 ...
686 views

### Making the player walk on walls in box2d

I'm making a game in stencil where players walk form left to right along randomly generated walls. I cant use waypoints, since the walls' shapes and positions are unpredictable. Here's a descriptive ...
1k views

### Do I need path finding to make AI avoid obstacles?

How do you know when a path-finding algorithm is really needed? There are contexts, where you just want to improve AI navigation to avoid an object, like a space -ship that won't crash on a planet ...
459 views

### About the A* algorith(pathfinding)

We have a formula of f=g+h wherein g is the path cost and h is the distance left to the goal. Given that I only want to move my unit in 4 direction (N,S,E,W), my question is: Can we consider h as ...
3k views

### A-Star Pathfinding Not Giving Shortest Path

I'm attempting to implement the A* pathfinding algorithm in Java. I thought it was working well, but then I found instances where it doesn't follow the shortest path Green = start, red = target, ...
352 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 ...
3k views

### How to do starcraft pathfinding?

I've been trying to figure out how to implement something like the pathfinding in Starcraft 2. I'm not looking for all the sophisticated features like flocking, queueing, etc. In fact I like how in ...
348 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 me,...
2k views

### Finding possible moves for an entity in a 2d tiled game

I'm having issues coming up with a specific search term for this, but how would one go about finding the possible moves in a 2D turn-based strategy game (i.e. FF:Tactics, Fire Emblem, Advance Wars). ...
326 views

### How can I use triangle picking to determine location of a triangle in world space coordinates?

I am trying to implement point and click movement in my game, but at the moment I am stumped about how I can select parts of a mesh for the player to walk to. So what I have done is I have got a ...
3k views

### In A star, how does the heuristic help determine your path?

Say you're using a 4 by 5 grid. The G cost for horizontal and vertical movement is 10, and the G cost for diagonal movement is 14. On this page: http://theory.stanford.edu/~amitp/GameProgramming/...
301 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 ...
160 views

### In A star, do I use the sum or the edge cost?

When you add a new node to the closed list, you need to check all the adjacent nodes. If you find any adjacent nodes on the open list, you have to check if G would be lower if you went through the ...
351 views

### What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how ...
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 clicked/...