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
1answer
247 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 ...
2
votes
2answers
189 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. ...
0
votes
0answers
358 views

NavMesh agents pushing other NavMesh Agents in Unity Pro

Using the NavMesh system in Unity, I created pathing system for my player character as well as the enemy AI. When a group of enemy NavMesh Agents surround my player character, they can be pushed out ...
4
votes
4answers
262 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. ...
4
votes
1answer
221 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 ...
5
votes
3answers
150 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 ...
12
votes
1answer
704 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 ...
1
vote
2answers
1k views

Is there a way to display navmesh agent path in Unity?

I'm currently making a prototype for a game I plan to develop. As far as I did, I managed to set up the navigation mesh and my navmeshagents. I would like to display the path they are following when ...
3
votes
1answer
439 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 ...
1
vote
3answers
285 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
220 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
163 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 ...
0
votes
1answer
273 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 ...
11
votes
3answers
702 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 ...
5
votes
1answer
410 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 ...
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 ...
0
votes
1answer
260 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
169 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
930 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 ...
6
votes
1answer
378 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 ...
2
votes
1answer
205 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
458 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). ...
5
votes
3answers
848 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
251 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
110 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 ...
2
votes
2answers
545 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 ...
5
votes
1answer
196 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 ...
1
vote
1answer
937 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
410 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
350 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 ...
3
votes
1answer
427 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, ...
0
votes
2answers
441 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 ...
2
votes
1answer
379 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
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
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 ...
3
votes
1answer
849 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
571 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, ...
1
vote
1answer
264 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 ...
6
votes
1answer
916 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
540 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 ...
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 ...
5
votes
1answer
192 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
155 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
3answers
910 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 ...
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 ...
-1
votes
3answers
309 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 ...
1
vote
1answer
193 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 ...
-1
votes
1answer
209 views

A* Search in games [closed]

I am making car racing game. I stuck with the AI of the game. I go through with the A* search, but there is problem that I want to ask that whether we have to make a 2D array and than apply search on ...
4
votes
1answer
363 views

Path finding in games

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;) So, i've done a little bit of searching ...