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)

4
votes
1answer
95 views

Cram search results into viewport (of a search minimap)?

I'm no coder, nor do I try to be. I just had one of those "it's impossible" arguments with folks who love to argue with me before they even understand what the argument is about :) So I need to ...
0
votes
1answer
127 views

Pathfinding Algorithms [closed]

I am new to game programming I currently am using unity's 2D power to remake an 2D game for sake of practice. So I am just little confuse about one thing, so far every enemy in my game was dumb(they ...
4
votes
1answer
108 views

Simplify navmesh path

I'm trying to implement pathfinding in my game, I'm using navmesh with triangles. I'm able to find a path but I want to simplify the path. This is what I have right now : Green quad is start ...
15
votes
4answers
4k views

Are square or hex grids better for pathfinding?

Is there any significant difference between using a square or hexagonal grid for the area searched by a path finding algorithm. In other words, is square or hexagonal better, and if so why.
3
votes
2answers
324 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
vote
2answers
720 views

Moving an object around the the circle to the specific location in circumference

Well I have run out of ideas how to approach this particular problem.See the picture below: So the idea is that the object (dot in black) has to get to a point mark X (red X mark).However the ...
2
votes
2answers
148 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 ...
3
votes
6answers
2k views

Pathfinding in multi goal, multi agent environment

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o). . . . a o . . . . . . . o . g . . a . . . . . . . . . . o . . . . o o ...
0
votes
4answers
339 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 ...
3
votes
2answers
707 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
134 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 ...
2
votes
2answers
1k 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 ...
11
votes
1answer
2k views

Efficient path-finding in free space

I've got a game situated in space, and I'd like to issue movement orders, which requires pathfinding. Now, it's my understanding that A* and such mostly apply to trees, and not empty space which does ...
4
votes
1answer
147 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 ...
0
votes
0answers
86 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 ...
21
votes
3answers
3k 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 ...
2
votes
1answer
465 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 ...
0
votes
2answers
250 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 ...
0
votes
1answer
50 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
1answer
93 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
185 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
votes
2answers
74 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
134 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
110 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; ...
59
votes
11answers
7k 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
733 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
1k 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 ...
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
33 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
1k 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
185 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 ...
3
votes
3answers
313 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
2answers
642 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 ...
1
vote
1answer
276 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
102 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
195 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
533 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 ...
1
vote
1answer
2k 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
130 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 ...
28
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
75 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
634 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
184 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
1k 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
1k 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
72 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
233 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 ...
3
votes
1answer
304 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
332 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 ...