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
2answers
862 views

Pointy top hexagonal A* pathfinding

I'm trying to create a game with a hex based map with the points at the top. I have most of it working, however the path finding is being a little awkward. The heuristic I'm using is called euclidian ...
-3
votes
1answer
590 views

c# xna move Image using two Vectors?

initially image placed (0,0)th position and where ever i touch that is end position. Now i got Start Position(0,0) and End Position(200,200). i want to move start to end vector using angle. If ...
2
votes
1answer
497 views

3D RTS pathfinding

I understand the A* algorithm, but I have some trouble doing it in 3D to suit the needs of my RTS Basically, in the game I'm making, there will be agents with different sizes of OBB collision boxes. ...
10
votes
1answer
1k 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 ...
3
votes
1answer
615 views

A* PathFinding Poor Performance

I'm getting poor performance in-game due to my path-finding algorithm. The farther I get from my NPC, the worse the framerate gets. Ok, I updated my code and implemented the openList as a min-heap ...
6
votes
4answers
2k 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 ...
0
votes
1answer
296 views

How do I make A* check all diagonal and orthogonal directions?

I'm making a turn-based tactical game and I'm trying to implement the A* algorithm. I've been following a tutorial and got to this point, but my characters can't move diagonally up and left. Can ...
-1
votes
2answers
300 views

How to spawn a character at certain point and walk to a set point

I am making a game where I have a background image of a neighborhood. Each location has a different number of customers that are generated to walk on sidewalks. They all walk to a specific location ...
4
votes
3answers
527 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
225 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 ...
0
votes
1answer
131 views

trouble in making a game questions?

all i've a little trouble understanding some concepts while making game please give your suggestions on my questions. I have a animated sprite image this i want to move this image according to given ...
2
votes
1answer
160 views

Level design: compute minimum time between two items for player traversal

Do any game toolsets offer a means of computing the minimum time it would take a player to move between two objects (or positions, more generally) in a level? I'm not asking about how one would go ...
0
votes
1answer
736 views

A* Pathfinding Problems

I'm trying to implement the a* pathfinding algorithm in my game. I've looked at dozens of tutorials but I can't seem to get it right. My code is below, and It's not working... does anybody see ...
3
votes
2answers
623 views

How to create wrap-around pathfinding?

I've created a planet and obstacle grid and want to move units through this grid using A* or any other algorithm. The only problem is wrapping. I need a simple example of how to handle this unusual ...
-4
votes
1answer
342 views

Multidimensional Pathfinding Algorithms

When trying to program hostile AI units for a war strategy game using pathfinder methods, do programmers ever have one algorithm for the unit to move and a separate algorithm for the unit to actively ...
5
votes
3answers
225 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
6k 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 ...
1
vote
1answer
272 views

How can I change the path a sprite is following in real time?

Is there a common way to implement a character following path that is issued and replaced in real time? For example: the character follows a path issued, and while it's on that path, if a new path is ...
5
votes
1answer
330 views

A* pathfinding algorithm to identify entrances into current “room”?

Was looking for some online articles that might have a good idea or two in how to approach this but not finding much. Most of it deals with the various ways to generate and follow a path to a known ...
0
votes
1answer
147 views

Copying section of map array

I'm experimenting a bit with pathfinding. I'm using Javascript. I have a map array as follows: mapArray = [ [0, 0, 0, 1, 1, 0], [1, 0, 0, 1, 0, 0], [0, 1, 0, ...
10
votes
1answer
1k views

Is precomputed pathfinding still relevant?

Context Old Lucas Arts (ScummVM era) point and click graphic adventure games used precomputed pathfinding. Here's a rough outline of the technique. Step 1 The floor in each room was divided into ...
9
votes
3answers
3k views

How do you do AI path following within a 2d physics engine like farseer/box2d?

I'm in the process of moving a 2d top down game I've been working on into a proper rigid body physics engine like Farseer. Up until now, I had just hacked together my own physics code where needed. ...
12
votes
1answer
4k views

A* navigational mesh path finding

So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world ...
3
votes
5answers
1k 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 ...
2
votes
3answers
424 views

Best way to implement mouse-based movement in MMOG

I want to design an MMO where players click the destination they want to walk to with their mouse and the character moves there, similar to Runescape in this manner. I think it should be easier than ...
0
votes
1answer
211 views

Good baseline size for an A* Search grid?

I'm working on a grid based game/prototype with a continuous open map, and are currently considering what size to make each segment. I've seen some articles mention different sizes, but most of them ...
2
votes
4answers
244 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 ...
1
vote
0answers
382 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 ...
3
votes
3answers
571 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 ...
11
votes
4answers
799 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
296 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
3k 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
4k 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 ...
8
votes
2answers
1k 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 ...
16
votes
6answers
747 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 ...
3
votes
2answers
676 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
565 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
933 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
761 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, ...
2
votes
1answer
993 views

Enemy Movement AI

I have a non-tile-based top down shooter game, and I have enemies set up. However I need the enemies to move to the player. Pathfinding algorithms will mean the enemies will just hug the wall. The map ...
6
votes
1answer
568 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
407 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 ...
16
votes
7answers
912 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 ...
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
136 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 ...
5
votes
4answers
239 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
399 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
459 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 ...