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
votes
2answers
59 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?
1
vote
1answer
76 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
101 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; ...
24
votes
3answers
16k 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.
55
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
671 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
825 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
1answer
263 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 ...
1
vote
0answers
31 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 ...
8
votes
1answer
953 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
122 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
212 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
231 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
5k 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
410 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
39 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
119 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
91 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
87 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
524 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
524 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
107 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
1k 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
4k 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
68 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
363 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
800 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
153 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
771 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
673 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
68 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
226 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
189 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
215 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 ...
48
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 ...
6
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
132 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
40 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
113 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 ...
3
votes
1answer
822 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 ...
0
votes
0answers
143 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
292 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
1answer
75 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 ...
17
votes
7answers
3k views

How do I make A* agents avoid other agents?

I'm implementing a multi agent A* algorithm on a tile map. Agents move only in the X and Y axes. I avoid collisions between them by checking where the others are when calculating paths. It works fine ...
3
votes
6answers
831 views

In what instances would you want to use path-finding algorithms other than A*?

I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right ...
0
votes
1answer
375 views

Box2d pathfinding using raytracing / predicted collisions

I have a Box2d/Cocos2d iOS game with enemies that attempt to follow the player (to attack). I'm working on improving the pathfinding logic so that the enemies won't crash into objects in the world. ...
3
votes
1answer
173 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 ...
1
vote
0answers
200 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 ...