Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
7
votes
1answer
918 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 ...
5
votes
4answers
218 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, ...
7
votes
2answers
309 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 ...
4
votes
4answers
369 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
353 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 ...
8
votes
2answers
1k views
pathfinding with obstacles in a Warcraft 3 like game
Consider A* searching on a tile based map. A straight forward code would be: If there is an unit inside that cell, then it is unreachable, this is ok.
But there is map resolution issue. When I look ...
2
votes
2answers
705 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
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 ...
1
vote
2answers
349 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
4
votes
2answers
1k 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
384 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
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 ...
12
votes
1answer
588 views
Is nVidia's CUDA suited to performing pathfinding calculations?
I want to know if it would be worth executing pathfinding on the GPU (using nVidia's CUDA, or an equivalent) in certain situations, or whether it would be a wasted effort. The situation I imagine ...
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 ...
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 ...
7
votes
5answers
2k 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.
...
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
2answers
371 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, ...
2
votes
1answer
697 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
3answers
1k 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 ...
9
votes
7answers
464 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 ...
8
votes
1answer
780 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* ...
15
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 ...
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 ...
7
votes
2answers
685 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.
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.
...
1
vote
1answer
563 views
Navmesh string pulling vs funneling
I'm creating a path-finder for navmesh. I'm wondering which method should I use after the A* has been completed, funneling or string pulling? What are the advantages/disadvantages of using them on a ...
3
votes
1answer
446 views
Sample Projects/Source for Navigational Meshes
Anyone aware of any sample source code that contain Navigational Meshes?
I'm aware of recast navigation (which is a little bit too complicated). - Written in C++.
Preferably C# but C++ is ok.
3
votes
2answers
1k views
How to handle pathfinding on a non-grid/non-node terrain map
I'm not sure if this is even path-finding. All I have is a 3D map that has hills, etc. I'd like the enemy to flock an object, but also walk around other objects. These blocking objects may be added ...
0
votes
3answers
1k 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.
2
votes
1answer
364 views
What tools are available for creating 3D collision and pathfinding data?
What is the process of creating geometry data to assist on NPCs movements and such on a 3D world to avoiding having them from going through the ground, etc? Are there specific modelling programs that ...
4
votes
3answers
687 views
What algorithm to use for path mapping?
I am making a turn based game with tiles, much like Final Fantasy Tactics.
I am trying to develop an algorithm for mapping out a list of available tiles to walk on.
So for example, I am at (0,0) and ...
5
votes
2answers
439 views
How do I apply A* to a complex and dynamic 3D environment?
So 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
...
9
votes
5answers
1k views
Longest path algorithm for roguelike maze generation
I have a simple grid-based map composed of rooms, like this (A=entrance, B=exit):
0 1 2 3
#########
0 #B# #####
#########
1 # ### #
#########
2 # # #
# # #
3 # # #
...
27
votes
7answers
7k 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 ...
10
votes
4answers
670 views
How do I make NPC pathfinding look believable?
Is there an "academic" way to have NPC walking randomly on a map, but having a believable comportment ?
The obvious scenario is a armed guard who is walking around a basement to secure it. It's quite ...
8
votes
3answers
554 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 ...
10
votes
2answers
334 views
How to compute the shortest path in Euclidean enviroments with non-convex polygons
Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles ?
thanks
13
votes
3answers
2k 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.
1
vote
2answers
229 views
What are some techniques used for mouse tracking, with a bit of “emulated lag”?
I am trying to implement a system, where the cursor (in my case the player's avatar) is always about 1.5 seconds (a configurable interval) behind where the mouse actually is. If I change the cursor's ...
8
votes
3answers
1k 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 ...
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 ...
24
votes
3answers
4k views
How does Flow Field pathfinding work?
Supreme Commander 2 has something called flow field path finding. How does it work? Is there some article available I can read up on how it works?
