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)

1
vote
1answer
114 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 ...
4
votes
1answer
208 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 ...
53
votes
11answers
4k views

How does A* pathfinding work?

I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
10
votes
1answer
591 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 ...
3
votes
1answer
397 views

How can I optimize this flood fill algorithm?

I'm creating a sprite and animation editor like this one. I'm having performance issues with my flood-fill algorithm. Basically, I open an image with the different modules that are part of a frame of ...
5
votes
1answer
325 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 ...
6
votes
1answer
346 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 ...
1
vote
2answers
172 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 ...
1
vote
3answers
270 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 ...
3
votes
2answers
213 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 ...
0
votes
1answer
154 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 ...
11
votes
3answers
694 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 ...
0
votes
1answer
260 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 ...
1
vote
2answers
489 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
2answers
412 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 ...
4
votes
1answer
371 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 ...
0
votes
1answer
257 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 ...
6
votes
3answers
1k 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, ...
2
votes
0answers
157 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 ...
3
votes
1answer
839 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 ...
2
votes
1answer
193 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 ...
6
votes
3answers
427 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). ...
1
vote
2answers
258 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 ...
5
votes
3answers
727 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: ...
2
votes
3answers
244 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 ...
1
vote
1answer
107 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 ...
5
votes
1answer
195 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 ...
2
votes
2answers
473 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 ...
1
vote
1answer
777 views

Prevent instances from overlapping gamemaker studio

I have a game where multiple instances of an enemy move towards a player in their step process. There can be as many as 50 instances on screen. The issue is that the instances all end up in 1 big ...
5
votes
1answer
369 views

Delaunay triangulation. Where to start?

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot ...
11
votes
1answer
339 views

Are there any pathfinding algorithms that would handle different movement types?

I'm developing a bot for a BattleTech board game simulator http://en.wikipedia.org/wiki/BattleTech, it is turn based. The board is divided into hexagons, each one has a different terrain type and ...
1
vote
1answer
254 views

Tiled based pathfinding in a 1- or 2-dimensional array

As far as I know all tile based map editors export a JSON object containing one dimensional arrays. While most pathfinding libraries/tutorials are only provided for two dimensional arrays. Also if ...
0
votes
2answers
403 views

Roguelike corridor creation; Connecting rooms

I have a simple Tile[,] that I populate with Rooms. Now I need to connect the rooms with a single tile wide corridor. At first I used A* to hook up the rooms but that, of course, get's the best path ...
3
votes
1answer
303 views

How do you construct a node map for pathfinding in a non-tiled 2D environment? [duplicate]

A* and Dijkstra's pathfinding algorithms work by navigating a node map. In a tile-based 2D environment, these nodes could easily be inferred to be the literal x,y positions of the map. For example, ...
2
votes
1answer
135 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
2answers
967 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 ...
3
votes
1answer
752 views

How to play character animation when using A* pathfinding

Hi I am trying to make racing game. In which I am using mecanim animation system to animate my character. Here are the conditions for the animation to play Speed --> 1 Run Speed --> ...
11
votes
4answers
541 views

How to determine range of possible movement in turn-based, distance-based strategy game?

I'm creating a 2-dimensional, turn-based strategy game using c++ and SFML-2.0. Movement is distance-based rather than grid-based, with several different triangle-shaped pieces that, on a given turn, ...
5
votes
1answer
780 views

Pathfinding with 2D, non-grid based movement over uniform terrain

I'm looking for the best solution to pathfinding in my game. The map is ultimately grid-based, but entities are positioned using floats, and can move in any direction to any point on the map. The ...
1
vote
3answers
509 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 ...
7
votes
1answer
275 views

Path Finding for an Arena based map in 3D using NavMesh

I have a 3D arena map (consider a small island surrounded by water on all sides) for a multiplayer Tank fight game. The moveable areas are marked using a Navigation Mesh made by the Arena designer. ...
2
votes
3answers
838 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
137 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 ...
5
votes
1answer
182 views

A* search in hexagonal grid with minimum turn radius

I need to run an A* search through a hexagonal grid. However, I have one nasty constraint: my vehicle can only turn so sharp. It has a specified minimum turn radius. I can't quite see how to translate ...
-1
votes
1answer
154 views

How to speed up AStar? [closed]

I have this AStar class, and at the movement it is INCREDIBLY slow. It takes waaay longer than I expected it too, and I'm not quite sure why. I added the generation part at the very beginning to ...
2
votes
1answer
205 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 ...
-1
votes
3answers
298 views

Looking for detailed pathfinding examples

I am currently working on a 2D-TopDown game. Now I was looking for pathfinding algorithms. I read and understood A* and Dijkstra. But there are still some questions I have. So I am looking for ...
23
votes
4answers
2k views

Is the Manhattan distance monotonic when used as heuristic function?

I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1. I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
3
votes
1answer
355 views

Fastest pathfinding for static node matrix

I'm programming a route finding routine in VB.NET for an online game I play, and I'm searching for the fastest route finding algorithm for my map type. The game takes place in space, with thousands ...
1
vote
1answer
175 views

Quick 3D sight calculation algorithm

I have a tile based board game where units move in 3D space on a 2D isometric view. When calculating attack tiles for a unit, how do I verify that they aren't shooting through a wall or a level too ...