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)

0
votes
1answer
27 views

Use pathfinding algorithm in a navmesh with several endpoints [on hold]

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
35 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
57 views

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

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
43 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 ...
2
votes
1answer
196 views

How to use an A* Pathfinding System across uneven environments?

I am developing a game in Unity3D. I want an enemy character to follow the player around. The problem is, my surface is uneven and full of mountains. I am using aarongranberg's pathfinding project. ...
-1
votes
2answers
33 views

Obstacles work in Unity Editor but not in the build [on hold]

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?
1
vote
1answer
64 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 ...
0
votes
1answer
85 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; ...
0
votes
4answers
114 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
2answers
195 views

A*Pathfinding lose target after spawning from script?

I have been using A*Path finding to enable object tracking. It works fine if I have both objects on the scene at the same time. However, if I were to use a script to spawn the seeking object ...
24
votes
3answers
14k views

How does Navigation Mesh path-finding work?

I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
54
votes
11answers
5k 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.
6
votes
2answers
622 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) ...
1
vote
1answer
536 views

How to follow object on CatmullRomSplines at constant speed (e.g. train and train carriage)?

I have a CatmullRomSpline, and using the very good example at https://github.com/libgdx/libgdx/wiki/Path-interface-%26-Splines I have my object moving at an even pace over the spline. Using a simple ...
2
votes
2answers
520 views

Using A*Pathfinding on terrain created by scripts?

I'm looking to use A* Path-finding as a method of navigating my game terrain. Trouble is, my terrain is built upon play using a script and A* grid does not detect this, therefore marking all nodes as ...
2
votes
1answer
220 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 ...
4
votes
2answers
1k views

Which pathfinding algorithm should I use for multiple enemies and tower placement?

I am new to game development and I am developing my first "Tower Defense"-type game. I need a pathfinding algorithm to place my towers and to move enemies. For tower placement case: I want the ...
2
votes
0answers
85 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
29 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
579 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 ...
2
votes
2answers
86 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 ...
0
votes
0answers
88 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
191 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 ...
1
vote
3answers
4k 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 ...
1
vote
2answers
286 views

How can I implement platformer pathfinding?

I've gone through A* pathfinding but could find anything on this. What I'm looking for is pathfinding for something kind of like a super smash bros level with different platforms. Can anyone point me ...
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
58 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
77 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
60 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 ...
5
votes
2answers
521 views

How do I apply A* to a complex and dynamic 3D environment?

I've looked a bit at Breadth-First and Depth-First search algorithms and I think I've got a pretty good idea of how they work. Now I am here : http://www.policyalmanac.org/games/aStarTutorial.htm ...
0
votes
1answer
168 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
75 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
1answer
991 views

Pathfinding with MicroPather : costs calculations with sectors and portals

I'm considering using micropather to help me with pathfinding. I'm not using a discrete map : I'm working in 2d with sectors and portales. However, I'm just wondering what is the best way to compute ...
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
59 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
226 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 ...
1
vote
2answers
410 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 ...
3
votes
2answers
144 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, ...
1
vote
2answers
433 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
2answers
319 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
1answer
219 views

Algorithm for staying “alive” forever

I am implementing a game where the player is playing(sliding) the little red rectangle and the purpose is to not hit the black rectangles and to not move out of the inner blue rectangle. The black ...
2
votes
1answer
137 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
3answers
148 views

Smooth path/direct movement

I have a tile based isometric map and an A* algorithm that returns a path. I am looking to smooth this path efficiently but with good aesthetics. Basically i am using my grid for building the map and ...
43
votes
5answers
2k views

Pathfinding for fleeing

As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B. But how do I calculate a path when an object is at ...
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
84 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
29 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
2answers
101 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 ...
8
votes
1answer
1k views

What are the disadvantages and/or limitations of navigation meshes?

I have a lot of materials on navigation meshes, what they are, their advantages over graphs made up of waypoints, etc. However, I haven't seen much information regarding the limitations and the ...