# Tagged Questions

Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

948 views

### Slow performance on an A* implementation in a tower defense game

I'm making a Tower Defense game in Flash with no predefined path. Although my grid is 40x40 (small?), A* is struggling when recalculating every time. So I made my own modification to ease the ...
2k 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). ...
7k views

### How can I generate a 2d navigation mesh in a dynamic environment at runtime?

So I've grasped how to use A* for path-finding, and I am able to use it on a grid. However, my game world is huge and I have many enemies moving toward the player, which is a moving target, so a grid ...
511 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 ...
2k views

### 2D pathfinding - finding smooth paths

I was trying to implement a simple pathfinding, but the outcome is less satisfactory than what I intended to achieve. The thing is units in games like Starcraft 2 move in all directions whereas units ...
461 views

### Estimating costs in a GOAP system

I'm currently developing a GOAP system in Java. An explanation of GOAP can be found at http://web.media.mit.edu/~jorkin/goap.html. Essentially, it's using A* to plot between Actions that mutate the ...
2k 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 ...
1k views

### Pathfinding with multiple random paths in a Tower Defense game

I thought about random pathfinding for my Tower Defense game. A* would not work for my puposes, because I specifically need random pathfinding. Imagine a map with routes, a starting point and a ...
631 views

### Should I share the same tile structure for display and pathfinding?

I know how to display a 2D map with tiles. I know how to make a pathfinding algorithm using A*. Those two things demand a structure or a class. My question is : do you use the same structure for ...
2k views

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 ...
501 views

### What alternatives exist of how an agent can follow the path calculated by a path-finding algorithm?

What alternatives exist of how an agent can follow the path calculated by a path-finding algorithm? I've seen that the most easy form is go to one point and when the agent has reached this point, ...
2k views

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 ...
191 views

### How do I calculate paths for objects with limited acceleration?

For example, say I have a car and a car has a specific minimum turning radius and I want to drive that car from point a to point b, but the car isn't facing point b. How do I compute a path to point ...
578 views

### Pathfinding and collision avoidance on mobile

Currently I'm developing a Diablo like game for mobile platform(iphone5+). A simple A* search will find the path, but collision avoidance still needs to be taken into consideration. There will be ...
2k views

### PacMan character AI suggestions for optimal next direction

Firstly, this is AI for PacMan and not the ghosts. I am writing an Android live wallpaper which plays PacMan around your icons. While it supports user suggestions via screen touches, the majority of ...
608 views

### Tile-wide extent tracing on a grid

I'm currently working on A* pathfinding on a grid and I'm looking to smooth the generated path, while also considering the extent of the character moving along it. I'm using a grid for the pathfinding,...
2k views

### Wikipedia A* pathfinding algorithm takes a lot of time

I've successfully implemented A* pathfinding in C# but it is very slow, and I don't understand why. I even tried not sorting the openNodes list but it's still the same. The map is 80x80, and there ...
4k views

### Best pathfinding algorithm for a tower-defense game? [duplicate]

What do you suggest would be the best algorithm for a tower-defense game? It's a 2D based tile game, where there is walls and towers blocking the way, between spawnpoints and their destination points. ...
2k views

### Tweaking AStar to find closest location to unreachable destination

I've implemented AStar in Java and it works ok for an area with obstacles where the chosen destination is reachable. However, when the destination is unreachable, the calculated "path" is in no way ...
801 views

### Low CPU/Memory/Memory-bandwith Pathfinding (maybe like in Warcraft 1)

Dijkstra and A* are all nice and popular but what kind of algorithm was used in Warcraft 1 for pathfinding? I remember that the enemy could get trapped in bowl-like caverns which means there were (...
591 views

### How to reference a map position in code?

I'm coding a digital version of the Macao board game which has a flat map similar to below. Players have a "ship" which starts in the blue box and can follow the dashed lines in any direction/...
803 views

### “Line of sight” path across navigation mesh

I want to calculate the line of sight in a navigation mesh. Consider the image below, the yellow line is the result of only A* and the red line is the result of a line of sight" algorithm that uses ...
1k views

### What heuristics are used in NavMeshes?

What heuristics do programmers use in A* pathfinding for NavMeshes? NavMesh = Navigation Mesh, its a type of pathfinding that uses meshes instead of waypoints.
3k 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 '...
159 views

### Cossacks game pathfinding

Cossacks (released in 2002) is an RTS game where you can build huge (few thousands men per player) armies on a really big maps. Imagine Age of Empires 2 for few players on Ludikris map with no lag, ...
2k views

### Path planning for volumes in games

How would you path plan a volume for a game? For example a 1 km cube with tunnels and caverns. Also the terrain is destructible. You have walking and flying modes. I would separate it into phases. ...
534 views

### Path finding between multiple maps

I'm interested in path finding between multiple maps - could be indoor/outdoor maps, different levels in a building etc but the main restraint is that there are one (or more) ingress/egress points ...
2k views

### Techniques for (literally) cutting corners on square grid maps

My game involves a level with deformable terrain and units that can travel in any direction but are slowed down by uneven terrain. Normal A-star should work fine in most cases, except on flat land ...
379 views

### Square Grid Polygonal Terrain Query algorithm?

I have a square, fixed-grid terrain with one terrain type per grid unit in my game, and I want to do an arbitrary polygonal terrain query which returns all of the grid units enclosed/intersected by ...
365 views

### 2D A* Path-Finding

I have this problem, which isn't really a problem, but I feel like it's some sort of glitch in my code maybe. My pathfinder, to find a path from A to B, does this: which is almost fine, it works ...
493 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. ...
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 ...
1k views

### How can I generate a (relatively) linear dungeon path?

We developing a concept for an action side-scroller. What we need is a way to generate a (relatively) straight map. By this I mean something like... It's clear to see that this map follows one ...
3k 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: http://theory.stanford.edu/~amitp/GameProgramming/...
3k views

### A-Star Pathfinding Not Giving Shortest Path

I'm attempting to implement the A* pathfinding algorithm in Java. I thought it was working well, but then I found instances where it doesn't follow the shortest path Green = start, red = target, ...
1k views

### Do I need path finding to make AI avoid obstacles?

How do you know when a path-finding algorithm is really needed? There are contexts, where you just want to improve AI navigation to avoid an object, like a space -ship that won't crash on a planet ...
749 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) ...
1k 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 ...
1k views

### Find nearest tile of type x

I currently have an array of tiles which makes up the tilemap (stored as an int array) and I want an NPC to be able to move itself to the nearest tile of type X (ie find the nearest tree and chop it ...
4k views

### Smoothing found path on grid

I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
889 views

### Correct way to handle path-finding collision matrix

Here is an example of me utilizing path finding. The red grid represents the grid utilized by my A* library to locate a distance. This picture is only an example, currently it is all calculated on ...
258 views

### How can I navigate to a target between bodies moving along fixed paths?

The problem: An autonomous ship starts at the outskirts of a solar system, and wants to move to a moving target, which is one of the planets. There are also many other planets moving at the same time, ...
328 views

### What is the difference between Djikstra and flow fields?

I understand flow field pathfinding (as illustrated in recent Gas Powered Games titles) consists of 1) computing a vector field covering the map for a given destination, 2) deriving unit directions ...
473 views

### Best pathfinding for a 2D world made by CPU Perlin Noise, with random start- and destinationpoints?

I have a world made by Perlin Noise. It's created on the CPU for consistency between several devices (yes, I know it takes time - I have my techniques that make it fast enough). Now, in my game you ...
1k 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 ...
255 views

### Pathfinding with inertia

I'm currently working for pathfinding for a game where units are moving, but they have inertia. Most typical pathfinding algorithms (A*, Djikastra, etc.) are simply designed to minimize the length of ...
829 views

### Implementing David Silver's Cooperative Pathfinding in Real-Time

I'm currently implementing David Silver's Cooperative Pathfinding algorithm for a 2D game with grid-based movement (all eight directions). The issue I'm having trouble wrapping my mind around is the ...
1k views

### Run-time Navigation Mesh Generation for 2D Tile Maps

I have a 2D tile map, where each tile is marked as blocking or non-blocking. Each tile is 16x16 pixels and sub-tile movement is possible. I'm attempting to generate a navigation mesh from this data, ...