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
2answers
40 views

Pathfinding in 3d voxel: waypoints?

I have an application where I have a 3d collision voxel space (passable or non-passable at each point) and I want to plot a short unobstructed path between two points. There are no gravity ...
1
vote
1answer
52 views

Best way to calculate city influence maps similar to civilisation?

As the title says, imagine you want to generate the influence mask for a city, given that the map is a 2D grid rather than hex. An extra bit is that different points on the map might have different ...
3
votes
1answer
75 views

Suboptimal A* Pathfinding Solution Example using Manhattan Distance Heuristic

I believe using an overestimating heuristic with A* is not guaranteed to find the shortest path. Assuming an agent can travel as a bird using euclidean distances, the manhattan distance provides just ...
1
vote
1answer
72 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 ...
0
votes
0answers
48 views

Pathfinding with move costs, grids, and arbitrary points

I'm building a game where the movement cost and passability is driven by a 2d array, but units are not conformed to this grid; it mostly just determines movement cost and natural/artificial immobile ...
2
votes
1answer
145 views

Pathfinding in a 2D “sidescrolling” strategy game

I've been thinking up a real-time strategy game that plays on a platformer type of map. The collidable portion of these maps will be made up of square tiles. I've done A* pathfinding in top down tile ...
18
votes
3answers
2k views

Why do some networked games use interpolation and some use pathfinding for remote movement?

This is a bit of an open question but I'd like to see someone contribute a good reasoning for both. For a quick example of both: Interpolation Model Think the Valve model where the client is ...
1
vote
2answers
78 views

Best way to constrain character to a path?

I'm in the process of developing a level-based runner for mobile phones, and I've hit a wall when deciding which method to use to get the character to move through the level. Basically - I need my ...
0
votes
0answers
25 views

Getting portals along a path of navigation nodes

I'm trying to create the path-finding algorithm for a small project and I'm having problems straightening the path after the A*-search returns a path along the navigation nodes (vertices of a ...
0
votes
1answer
35 views

Use pathfinding algorithm in a navmesh with several endpoints [closed]

I need to implement a pathfinding algorithm in a navmesh with several endpoints, and I would like to find the path to the closest endpoint. I suppose that Dijkstra algorithm is the best solution for ...
0
votes
0answers
49 views

Dijkstra Pathfinding in Libgdx, some minor problems

I'm having some problems with my Dijkstra implementation in Libgdx. I understand that there are already AI libraries that can probably do this much simplier but this is a school assignment so i'm ...
0
votes
1answer
65 views

A* pathfinding not finding shortest path with weird behavior [closed]

NOTE I have read through this thread and have tried the implemented answer The A* pathfinding algorithm works fine most of the time but in some specific cases, it seems to not use the shortest path. ...
2
votes
2answers
52 views

A* pathfinding for grid with direction-dependent nodes?

I'm trying to understand if the A* algorithm is a possible pathfinding solution for my game. I have a simple grid of nodes that an enemy can move around on, but the nodes represent traversable ...
1
vote
1answer
67 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
votes
2answers
35 views

Obstacles work in Unity Editor but not in the build [closed]

As the title states my code works in editor view but not when I Build it. I need to dynamically place and remove Obstacles in a NavMesh. Can anyone give some insight why this happens?
0
votes
1answer
93 views

Game mechanic player following path looks very roughly

I want my player entity to follow a path, which works, but it looks very roughly. Like it would stuck everytime. bool arrivedX = false; bool arrivedY = false; float speed = 0.06f; ...
6
votes
2answers
638 views

Getting a Ranged AI “In Range” to shoot

In my game, ranged units and melee units have the same behavior. Ranged units try to maintain a fixed distance r, from their targets. If they're within r + d of the target (where d is a small value) ...
2
votes
1answer
234 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
1answer
117 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 ...
1
vote
0answers
30 views

Optimization of A* in Python [duplicate]

I am working on an IA (in Python) for small board game, and I need to do a lot of pathfinding per round in order to find the best move I can do (minmax implementation). My problem is that even if the ...
6
votes
1answer
633 views

Pathfinding: Tile-Based Navigation Mesh

I'm developing a real time, tile-based RTS. This is an example map: This map consists of 4 regions with 256 tiles each. Blue tiles represent obstacles. Units can move in the standard eight ...
0
votes
0answers
117 views

Generating a NavMesh / Point Graph for 2D Procedural Platformer Levels

I am trying to create an algorithm which handles a NavMesh / Point Graph Generation for 2D Procedural Platforms Level in Unity3D. The reason why I say NavMesh / Point Graph is I don't know which one ...
3
votes
3answers
201 views

Possible A* Optimizations [closed]

I have implemented A* in my game. However, I am not happy with the performance and need some help deciding what to do next. I have already done the following optimizations: Not having a closed ...
0
votes
0answers
37 views

2D Platformer Pathfinding [duplicate]

First of all, I'm sorry, I know this is a really broad topic, but I've been trying to do this for days, I've looked at about a hundred different Google links, and I'm just not having any luck. ...
0
votes
1answer
68 views

Path finding for Vector Based System

I understand that typical path algorithms are based on nodes in a graph (not tiled nodes or whatever), but i can't get my head around to find an idea how to implement a path finding algorithm for a ...
0
votes
1answer
84 views

Basic Monster Movement

I'm new to game development. Specifically server side. Currently I am trying to implement movement of monsters. From point A to point B. I have used an a* pathfinding library to calculate the path to ...
0
votes
1answer
64 views

Backtracking in A Star

Hello, can anyone tell me how can i implement backtracking in a a star search algorithm? I've implemented the a star search according to wiki, but it does not backtrack, what i mean by backtrack is ...
0
votes
4answers
140 views

AStar for isometric game with overlapping walkable areas

We're developing an isometric game that so far has had a single ground level (y = 0) for the avatar to walk on. Pathfinding for this can be solved with a relatively simple 2D AStar tile map. We're ...
0
votes
1answer
227 views

A* pathfinding in 3D

I've looked through some A* pathfinding algorithm examples, but as far as i know they work with grids e.q -> http://qiao.github.io/PathFinding.js/visual/ But how can I use this algorithm in my 3D ...
0
votes
1answer
82 views

Logic for enemy chasing main player

I'm making AI to tell a minion to chase and attack the player. I played Magicka, and the minion follows the player in a nice curved manner (left image), rather than what I currently have (right ...
2
votes
2answers
93 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 ...
5
votes
3answers
239 views

How can I do optimal pathfinding for a Tetris piece?

Imagine a standard Tetris board (10x20) using the standard set of 7 tetrominos. Given a Tetris game state and a target position, how can I find the optimal sequence of moves that will get the ...
3
votes
2answers
146 views

How should I store a city map on disk?

I'm working on a game where players travel in a city. This city is defined by streets (names, positions...), points of interest (cinemas, restaurants...) and different zones (high criminality zones, ...
23
votes
12answers
3k views

How can I make A* finish faster when the destination is impassable?

I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an ...
1
vote
2answers
386 views

How can I highlight and move to adjacent tiles in an isometric grid?

I trying to create a turn-based strategy game where you move a game object from one tile of a grid to another tile near it. I have created the grid using sprites and game objects but can't sort out ...
0
votes
1answer
64 views

A* pathfinding question [duplicate]

http://i62.tinypic.com/23hlgcg.jpg im trying to get a grasp on the A* pathfinding algorithm. Using the image i attached. if the green square represents the start, and red represents the end. wouldn't ...
1
vote
2answers
61 views

nurbs and pathfinding optimization

I'm working on a project, and my current milestone is pathfinding. I have a working prototype that consists of several components: a manually drawing of a path, that matches the visual path that the ...
5
votes
3answers
1k views

How to find path in graph without crossing the walls?

I would like to know how to find path in a graph while having the edges "double-sided". Consider this scenario: I have list of the line segments. These represents "walls" or rather impassable edges ...
0
votes
0answers
94 views

Triangulation of “polygon with holes” for NavMesh

Just for fun, I am working on a little side-project: As a first step, I want to be able to build a grid-based world (think Dungeon Keeper), generate a nav-mesh for this world and then let agents ...
0
votes
0answers
30 views

Using Flash IDE to link nodes for Dijkstra algorithm

I'm trying to use plash to set up the node connections, but having a really hard time to use the IDE as a tool to do so. Before giving up completely, and getting into creating a tool that would take ...
2
votes
1answer
145 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
108 views

How to convert non-discreate data for discreate pathfinding?

I have a list of entities that looks like [{x,y,width,height}, {x,y,width,height}, ...]. This list is non-discreate, It doesn't follow a grid. entities can be positioned at floats like x:2.345 Most ...
0
votes
0answers
90 views

Changing a single component of a prefab?

I'm working on a unity project and I'm looking to show the range of a certain character. However, the terrain is generated through a script at run time, and considering that the script uses the ...
0
votes
2answers
281 views

Why does my A* implementation overflow the stack?

I'm fairly new to game dev and working on my first ever attempt at 2D pathfinding. I'm using the A* algorithm as detailed here. For the most part, it seems to be working correctly and as intended. ...
1
vote
2answers
493 views

Game Maker: Studio - Make objects avoid other instances of same object with A* pathfinding

I have a game where there are multiple enemies who must chase a single player. I have pathfinding set up using the GML A* pathfinding with mp_grid and a path. However, these enemies can walk on top ...
1
vote
2answers
534 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, ...
1
vote
1answer
74 views

How can I do a weighted cascade down a path in a 3D environment?

I am trying to perform a weighted cascade down a path in a 3D environment. Now, what I am trying to do is have one object(a cube) in the environment scan from its coords 1 in every direction for ...
3
votes
1answer
126 views

How are flow fields different from potential fields?

I've heard of of both flow fields and potential fields for pathfinding in games. They sound similar, but I never see them mentioned in the same contexts. Places that mention one never mention the ...
2
votes
1answer
129 views

Aligning pathfinding to the center of tiles?

I'm looking to achieve tile by tile movement in a project I'm working on. I employed the use of the asset Simply A* Path-finding to allow a unit to navigate the terrain. Since the tiles are ...
1
vote
0answers
140 views

Square tile navigation unity

I'm looking to generate a grid style navigation system in Unity. I have created a map in Tiled and am unsure how to continue considering the tiles will have different properties. The closest example ...