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)

2
votes
4answers
240 views

Path tables or real time searching for AI?

What is the more common practice in commercial games; path lookup tables or real time searches? I've read that in many games path lookup tables are pre-calculated and baked into each map, so to ...
3
votes
3answers
540 views

Tool for creating complex paths?

I want to create some fairly complex 2d predefined paths for my AI sprites to follow. I'll need to use curves, splines etc to get the effect I want. Is there a drawing tool out there that will allow ...
1
vote
0answers
377 views

Stuck with A* implementation [closed]

I have implemented some A* code in C# using this JavaScript code. My C# implementation is the same as the above javascript code. But I'm unable to get it to work properly, e.g pathfinder blocks ...
5
votes
4answers
1k views

One Step-Ahead A-Star

I am attempting to create a server-centric RTS (as opposed to usual parallel synchronised simulation route of most RTS games today) - however I am still leveraging the discreet N-turns-ahead paradigm ...
11
votes
4answers
710 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
282 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 ...
0
votes
1answer
2k views

Basic A star implementation tutorial [duplicate]

Possible Duplicate: Pseudo-code examples of A*? Hey guys Iam making a TD game and now I am stucked in implementing A star algo. I know there are many 3d party softwares but they are ...
3
votes
3answers
3k views

Pseudo-code examples of A*?

I'm looking for pseudo-code examples of the A* pathfinding algorithm that actually works. I tried plenty of different ones where it's not really clear how to implement them at all times. Keep in mind ...
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 ...
16
votes
6answers
719 views

Making the AI take different paths to each other

I have a top down 2d game where the AI spawn at the edges of the map and run towards the center. I'm using A* and a node mesh to do the pathfinding. Right now, the AI spawn at a point on the edge of ...
5
votes
4answers
230 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, ...
3
votes
2answers
573 views

Multi-tile agent path-finding algorithm?

Suppose we have a uniform rectanglular grid as shown below. The a is an agent, o is obstacle and g is goal. What are the options of handling multitile agents (e.g. dragons or tanks)? . . . . o . ...
10
votes
5answers
530 views

Situational awareness in path finding

Assume you had to find the shortest path through a dungeon, where certain passages are only opened to you after certain items were collected, like locked doors and keys, for instance. The normal gut ...
8
votes
1answer
799 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 ...
5
votes
1answer
661 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, ...
16
votes
7answers
878 views

Spawning units in a world made by Perlin noise?

There's some issues that I've come across in my Perlin noise-based game. Take a look at the attached screenshot below. The white areas you see are walls, and the black areas are walkable. The ...
2
votes
1answer
380 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 ...
5
votes
5answers
1k 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. ...
0
votes
2answers
134 views

Converting 2d path to 3d path

What is the procedure to convert 2d path to 3d one. Maybe it's a silly question, but for example: Let's assume that I have a path from point A to point B. And I have all X and Y coordinates of that ...
7
votes
1answer
1k 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 ...
4
votes
4answers
433 views

How can I make my units follow predetermined paths?

I'm planning my first game and am planning on using the engine set out in Beginning Android Games, as it deals with a load of stuff that is just noise at the moment to me (because I've no real world ...
3
votes
2answers
443 views

Path-finding algorithms for Polar coordinate based maze?

Following on from my question about moving a sprite in a circle, assuming that you have a maze which is shaped like a a set of circles with holes in them and barriers between them. Location of a ...
2
votes
2answers
851 views

Are there any usable performant path-finding libraries for python?

This is cross-posted from StackOverflow, please feel free to answer there too: I'm working on a real-time isometric RPG in python, and wish to target mobile devices as a platform. The main area where ...
3
votes
2answers
512 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 ...
24
votes
3answers
10k 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.
28
votes
7answers
9k views

How does pathfinding in RTS games work?

[crossposted from stackoverflow] In a game such as Warcraft 3 or Age of Empires, the ways that an AI opponent can move about the map seem almost limitless. The maps are huge and the position of other ...
1
vote
2answers
478 views

A* only for horizontal / vertical movement

anyone can share a link for a tutorial or article about optimizing A* for horizontal / vertical movement (no diagonal). Is not as easy as change the G values to 10 everytime. Thanks
16
votes
6answers
1k views

AI control for a ship with physics model

I am looking for ideas how to implement following in 2D space. Unfortunately I don't know much about AI/path finding/autonomous control yet. Let's say this ship can move freely but it has mass and ...
7
votes
2answers
2k views

How to calculate the vector of an interception?

Given are a twodimensional space, and 1 friendly spaceship standing still, one foe is moving NOT directly to the friendly ship with known actual position, speed and direction. The friendly ship wants ...
27
votes
6answers
2k views

what is the standard solution to pathfinding towards a moving target?

I am working on a 2D RTS like game, basic A* works perfectly for moving a unit from point A to point B. But now I facing the continuous path-finding problem, like A attack a moving object B, call A* ...
8
votes
2answers
455 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 ...
2
votes
2answers
876 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
150 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
685 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 ...
14
votes
9answers
5k 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 ...
7
votes
5answers
3k 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. ...
8
votes
5answers
986 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. ...
12
votes
3answers
4k 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 ...
9
votes
1answer
417 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 ...
7
votes
3answers
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 ...
9
votes
5answers
877 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 ...
8
votes
2answers
414 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, ...
9
votes
7answers
479 views

How should I replan A*?

I've got a pathfinding boss enemy that seeks the player using the A* algorithm. It's a pretty complex environment, and I'm doing it in Flash, so the search can get a bit slow when it's searching over ...
10
votes
3answers
2k views

Moving around/avoiding obstacles

I would like to write a "game", where you can place an obstacle (red), and then the black dot tries to avoid it, and get to the green target. I'm using a very easy way to avoid it, if the black dot is ...
2
votes
1answer
842 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 ...
9
votes
1answer
1k 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* ...
6
votes
7answers
1k 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 ...
0
votes
3answers
2k views

Node-Based pathfinding vs A* and others

Whats the difference between node-based pathfinding algorithm and the A* among others? A friend just told me about node-based, but I cannot find much tutorial or information on it.
14
votes
3answers
3k 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.
7
votes
2answers
835 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.