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)

6
votes
3answers
367 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
243 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
468 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
231 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
96 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
186 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
325 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
429 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
276 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
314 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
229 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
321 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
205 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
131 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
660 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
522 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
475 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
593 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
418 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
256 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
677 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
133 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
152 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
142 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
180 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
265 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 ...
22
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
326 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 ...
0
votes
1answer
145 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
207 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 ...
1
vote
3answers
1k views

Pathfinding library

I'm an amateur game developer and somewhat amateur Java developer as well. I'm trying to find a way to have path finding for my game(s). I've first Googled for some existing Java libraries that have ...
10
votes
5answers
1k views

Longest path algorithm for roguelike maze generation

I have a simple grid-based map composed of rooms, like this (A=entrance, B=exit): 0 1 2 3 ######### 0 #B# ##### ######### 1 # ### # ######### 2 # # # # # # 3 # # # ...
4
votes
1answer
321 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 ...
3
votes
1answer
110 views

How to create a path-finding compatible road map from user input?

I'm currently working on an agent simulation (inspired by the recent SimCity release). Now, basically I understood how agents work but I do not understand how to put them into context. Agents travel ...
8
votes
2answers
1k views

Is Jump Point Search (A* with JPS) appliable to non-diagonal grids?

I'm trying to speed up my pathfinding and discovered A* with JPS. It basically prunes tiles before adding them to the OPEN set. Can I use that technique with my grid that only allows straight ...
0
votes
0answers
48 views

How to modify graph ingame?

The pathfinding in my game uses this function to generate a graph: def make_graph(self, size, impassable): nodes = [[astar_gridnode(x, y) for y in range(size)] for x in range(size)] graph = ...
8
votes
2answers
367 views

Drone targeting

Imagine a "drone" and a target point on a 2d plane. There are eight parameters: P = my position Q = target position V = my velocity I = my moment of inertia w = my angular velocity s = my angular ...
13
votes
2answers
769 views

Partially observable game map — is A* appropriate?

I know very little about game development and I'm trying to wrap my head around pathfinding algorithms. Consider this setup: an agent is on a 2D map and must find the shortest path to a globally know ...
1
vote
2answers
383 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 ...
4
votes
1answer
301 views

Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of ...
-1
votes
1answer
340 views

Ways to achieve path finding on android [closed]

I have spent two weeks on this task and its to no avail,i hope your expertise can help me. I want to create a simple set of activities that allow the shortest path to be calculated between two points ...
11
votes
1answer
927 views

Pathfinding on a uneven planetary surface

My question is what would be the best approach to pathfinding on an uneven planetary surface? Background Information I have created a planet from displacement mapping 6 sphere projected planes. ...
1
vote
2answers
5k views

How can i use A star pathfinding algorithm

How would i implement an A star algorithm for a game that i'm making on the android in java? i'm looking for a pre-made A star API in java with classes and methods to call. i don't want to have to ...
3
votes
1answer
191 views

How can I find all shortest paths using A*?

It is possible for A* Path Finding to return all the shortest paths given a graph/map? For example, given the map below: ----------- --a--X--b-- ----------- The said map can return four (4) ...
0
votes
1answer
321 views

Pathfinding with different sized units [duplicate]

I am actually working on a general purpose pathfinding library (find it here), mostly oriented for grid-based maps. I was looking for ways to integrate support for pathfinding with units of different ...
3
votes
2answers
310 views

How Does Ultima 7 manage different floors in 2d

In U7, you can move among floors without the function "tranport" the player to another place, as for example the first ff ones. How can it tell whenever the character is moving from floor z to ...
6
votes
2answers
766 views

Creating a navmesh from a voxel terrain

My world is represented by a 3D density field, where a positive density means solid ground and a negative (or zero) density means air. How can I generate a navmesh from that voxel data, with surfaces ...
28
votes
3answers
6k views

How does Flow Field pathfinding work?

Supreme Commander 2 has something called flow field path finding. How does it work? Is there some article available I can read up on how it works?
2
votes
1answer
147 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 ...
1
vote
2answers
222 views

How to get characters to be aware that their path is obstructed?

I'm using Unity with Arongranberg's A* pathfinding project to move my characters. However, it appears that my characters are contending for a position on the terrain when they are told to move ...