Tagged Questions

13
votes
2answers
617 views

Partially observable game map — is A* appropriate?

I know very little about game development and I'm trying to wrap my head around pathfinding algorithms. Consider this setup: an agent is on a 2D map and must find the shortest path to a globally know ...
4
votes
1answer
205 views

Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of ...
8
votes
2answers
288 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 ...
6
votes
0answers
153 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. ...
0
votes
0answers
97 views

How to predict encounters between a ship and a body's sphere of influence in 2D

Long time listener, first time caller. I'm making a little hobby game in XNA, its about transport ships in space, analogous to container ships at sea. There are to be AI ships and player controlled ...
9
votes
3answers
495 views

Algorithm to see if two voxels are interconnected

I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to ...
5
votes
3answers
293 views

3D pathing finding with flying

Does anyone know of a (free or paid) solution that enables 3D path finding? Basically something like: CalculateRoute(input_geometry, start_pos, end_pos, variance) I found a good paper on the ...
0
votes
1answer
65 views

make a character walk along a defined path(as much as possible)

What I want is a character walking along a path, which is defined as a sequence of waypoints. For example, a soldier patrol around a castle. The problem is, I want the soldier to avoid (dynamic) ...
2
votes
4answers
532 views

Efficient path-finding on 2D tile-based multilevel map

It's a question I've been thinking about for some time... How do you effiently find a path on a 2D tile-based multilevel map? The map I use, for example, is 2048 on 2048 tiles wide. It has 14 levels ...
2
votes
2answers
132 views

Prevent collisions between mobs/npcs/units piloted by computer AI : How to avoid mobile obstacles?

Lets says we have character a starting at point A and character b starting at point B. character a is headed to point B and character b is headed to point A. There are several simple ways to find the ...
5
votes
1answer
98 views

trapped inside a Graph : Find paths along edges that do not cross any edges

This is a graph based platformer level and the round shapes are creatures. I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the ...
7
votes
2answers
480 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 ...
0
votes
1answer
122 views

How can I locate empty space next to polygon regions?

Let's say I have the following area in a top-down map: The circle is the player, the black square is an obstacle, and the grey polygons with red borders are walk-able areas that will be used as a ...
5
votes
4answers
356 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 ...
0
votes
1answer
369 views

Pathfinding using nodes/waypoints without connecting them?

I've been doing some research on pathfinding lately because I want to code a game modification for a game (won't say which exactly) and what I've done is defined a huge list of 3D vectors where a ...
4
votes
4answers
966 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 ...
4
votes
3answers
311 views

Creating the nodes for path finding during run time - more like path making and more

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question. It's a 2d turn-based ...
1
vote
1answer
199 views

A* and Space partitioning

I'm planning on implementing A* in my game for pathfinding, I understand the basics of how the algorithm works but I was wondering, other than finding the start and end nodes Are there any benefits to ...
5
votes
3answers
203 views

A* : Partial recalculation when one node *changes*

I have implemented an A* library. Its most interesting feature is that it is "interruptible"; for example, you can stop the calculation loop on a game frame, and resume it later on the following ...
1
vote
2answers
3k views

How can i use A star pathfinding algorithm

How would i implement an A star algorithm for a game that i'm making on the android in java? i'm looking for a pre-made A star API in java with classes and methods to call. i don't want to have to ...
11
votes
4answers
528 views

How do I get AI Agents to move along a curve?

Currently my very basic AI framework has agents that move along a a jagged path made up of a series of points. They do this by simply moving their position from one point to the next. When they ...
2
votes
1answer
247 views

Dynamically creating astar node map by triangular polygonal map

My game's map format uses a bunch of triangles to make up the platforms and terrain in 2d. Right now I can set up a 2d array of nodes for the astar algorithm that basically is a bunch of rectangles ...
6
votes
1answer
545 views

Linking nodes algoritm for Visual Design

I'm developing an editor for my game, and now it's time to make a visual scripting system to let designer modify behaviours. This video shows what i have done and the problem to resolve the link ...
2
votes
1answer
314 views

All Pairs Shortest Paths in Weighted Undirected Graph

I'm currently working on path-finding for my game and need help with finding an efficient algorithm to calculating the all-pairs shortest paths in a weighted undirected graph (each vertex in the graph ...
3
votes
2answers
469 views

How does Half Life's covering work?

Enemies in this game take cover. AFAIK HL uses some logical decisions for enemy to start searching for cover and to abandon cover, and I am able so far to find them; but how does he find a cover ...
2
votes
2answers
616 views

Path finding in grid for objects that occupy more than one tile

In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
3
votes
1answer
136 views

Coordinate based travel through multi-line path over elapsed time

I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because ...
3
votes
2answers
551 views

Infinite loop during A* algorithm

The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate ...
3
votes
3answers
1k views

Which algorithm used in Advance Wars type turn based games

Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to ...
10
votes
3answers
2k views

Real Time Dynamic Pathfinding?

I'm currently doing some pathfinding research and my simulation is the following: I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
6
votes
3answers
887 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 ...
8
votes
1answer
778 views

Triangulation A* (TA*) pathfinding algorithm

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81. He describes how to adapt the regular A* ...
8
votes
5answers
921 views

Why is Reinforcement Learning so rarely used in pathfinding?

The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development. ...
8
votes
5answers
827 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 ...
9
votes
1answer
388 views

Locate the shortest path through obstacles when all normal paths are blocked

I'm making a Tower Defense and I have basic pathfinding working, but I got a problem. I want to make the path blockable, and when a block occurs the runners will attack the blocking towers. So what ...
21
votes
3answers
7k 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.
13
votes
9answers
4k views

Dynamic pathing algorithm for tower defense game

I'm making a Tower Defense and I need a good pathing algorithm for it. I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or ...
3
votes
5answers
583 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 ...
45
votes
11answers
3k 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.