# Tagged Questions

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

112 views

### Path finding to collect enough items before the fight with the enemy

So I have the following problem : a X by Y grid. On the grid there is a character and a monster and some items that give bonus points to the character's damage if picked and holes that must be avoided....
357 views

### How Does Ultima 7 manage different floors in 2d

In U7, you can move among floors without the function "tranport" the player to another place, as for example the first ff ones. How can it tell whenever the character is moving from floor z to ...
265 views

### Wander algorithm for a maze [duplicate]

I am making a multiplayer coop FPS game. I have created the first monster with it's AI. I have worked out the A* algorithm for the level based on the triangles of the walkable mesh. So I can already ...
1k views

### How to get characters to be aware that their path is obstructed?

I'm using Unity with Arongranberg's A* pathfinding project to move my characters. However, it appears that my characters are contending for a position on the terrain when they are told to move ...
162 views

### Travelling in a 2D grid

I have a 2D grid (x,y coordinates) where each cell corresponds to each pixel of the interface that I am working with and I have a point A(x1,y1). Now I need to travel around in the grid, and I wont ...
682 views

### Making the player walk on walls in box2d

I'm making a game in stencil where players walk form left to right along randomly generated walls. I cant use waypoints, since the walls' shapes and positions are unpredictable. Here's a descriptive ...
325 views

### How can I use triangle picking to determine location of a triangle in world space coordinates?

I am trying to implement point and click movement in my game, but at the moment I am stumped about how I can select parts of a mesh for the player to walk to. So what I have done is I have got a ...
1k 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 ...
200 views

### Path-finding with obstacles that can be destroyed

There are several buildings on the map with size n * n， and a lot of tiles of obstacles that can be destroyed. Suppose I put one soldier on (x,y) of the map, the soldier can reach a building by ...
2k views

### How to make a gui button follow a path after a touch?

I would like a button in my gui menu to follow a specific path if we selected it, I am wondering how I could do it: if we touch the button, then it can only move on the specific path, it is an arc ...
282 views

### A* for non grid network

For my specific case, I am trying to find a path finding implementation similar to what described here. I could see reference implementation for A* and HPA*, but I wonder how to extend A* to simple ...
624 views

I'm designing a 2d RPG where you navigate on a overhead map. The terrain is mostly open with big parts of inaccessible terrain such as mountains and rivers. The player navigates short distances at a ...
3k 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 topic,...
309 views

### Pathfiding for groups of agents

How can we refine this path search method to make group movement more elegant? I'm trying to make a RTS-style game, using a 2d tiled gameworld. I have implemented an A* pathfinding algorithm which ...
3k views

### NavMeshAgent in Unity giving jerky performance

I am using NavMeshAgent in my Unity project to calculate and move my object to a particular location. When I do: navMeshAgent.destination = destinationPt the object starts moving, but the motion ...
123 views

### How do I avoid obstacles on a predefined path?

I want is a character to walk along a path defined as a waypoint sequence. For example, a soldier patrolling around a castle. However, I want the soldier to avoid (dynamic) obstacles, without ...
725 views

### Moving an object around the the circle to the specific location in circumference

Well I have run out of ideas how to approach this particular problem.See the picture below: So the idea is that the object (dot in black) has to get to a point mark X (red X mark).However the ...
75 views

### How to find which dirction to move in a 3D space [closed]

In my game you are controlling a person walking(X and Y) and they can: Rotate view - -180 to +180 Move a direction - Forward, Backwards, Left, Right. I want the Move to get closer to a goal ...
278 views

### Walk to nearest attackable range node

My game has 3D environment which is partitioned in 2d cells(nodes). I have implemented A* for path finding. Now I am just breaking my head to how to implement the algorithm to move the hero to the ...
544 views

### How to handle entity path-finding and movement in a large networked world?

Considering the image above with tiles split into 32x32 boxes, I have an entity which is marked to 'aggro' nearby players that come close to it. I'd like this monster to ideally chase the player (and ...
807 views

### How to determine that nodes in Grid Graph are unreachable before applying pathfinding?

I would like to determine accessibility of nodes before applying pathfinding algorithm to Grid Graph. I have a surface with nodes overlayed on it and I would like to somehow determine that nodes ...
802 views

### A* mouse movement javascript top-down game

Im trying to implement a* path finding for my character movement in my game. The game is written in javaScript along with jQuery in a canvas. I have read up on A* so i believe i understand what it ...
2k views

### How to make my characters turn smoothy while walking on a path(list of coordinates)?

I have a list with coordinates - output from A* algorithm - and I would like to make my characters smoothly follow this path with rotations. So I have something like A and I want to get C How can ...
701 views

### Working with chunks of terrain

Let's take for example that in our game, we divide our world (1000x1000 tiles) into chunks of 100x100 tiles. Each chunk contains its own npcs, traps, players, items, whatever. Now, there comes to my ...
2k 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 ...
198 views

### Astar heuristics closing in on an answer before searching around to find nodes with lower movement costs

I am having some trouble with my A* path finding. everything works fine and the path is always found. However, my game is a open map space strategy game. There are no walls etc to navigate around. Now,...
178 views

### Complexity of defense AI

I have a non-released game, and currently it's only possible to play with another human being. As the game rules are made up by me, I think it would be great if new players could learn basic game play ...
116 views

### Should pathfinder in A* hold closedSet and openedSet or each object should hold its sets?

I am about to implement A* pathfinding algorithm and I wonder how should I implement this - from the point of view of architecture. I have the pathfinder as a class - I think I will instantiate only ...
781 views

### Dynamic obstacles avoidance in navigation mesh system

I've built my path finding system with unreal engine, somehow the path finding part works just fine while i can't find a proper way to solve dynamic obstacles avoidance problem. My characters are ...
454 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 ...
426 views

### What's the best way to move cars along roads

I am implementing car movement game (sort-of like Locomotion). So 60 times a second I have to advance the movement of each car. The problem is I have to look ahead to see if there is a slower car, ...
96 views

### Detecting if an object is following a path

I am attempting to take GPS data and track it on a map and see if it follows a given path. I have the path as a set of points and the GPS data streams in as a similar set of points. I am attempting to ...
4k views

### Finding shortest path on a hexagonal grid

I'm writing a turn based game that has some simulation elements. One task i'm hung up on currently is with path finding. What I want to do is, each turn, move an ai adventurer one tile closer to his ...
402 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 ...
1k views

### Making an AI walk on a NavigationMesh (2D/Top-Down game)

For some time I have been working on a framework which should make it possible to generate 2D levels based on a set of rules specified by level designers. You can read more about it here as I won't go ...
3k views

### Pathfinding for fleeing

As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B. But how do I calculate a path when an object is at ...
671 views

### Influence Maps for Pathfinding?

I'm taking the plunge and am getting into game dev, it's been going well but I've got stuck on a problem. I have a maze that is 100x100 with 0,1 to indicate if its a path or a wall. Within the maze ...
168 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 ...
151 views

### How to select a random node [closed]

I need to know if it is possible to select a random node or select a node itself because I'm doing a zombie AI and I need him to randomly move, and I wanted to know if it's possible to do it and how.
470 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 ...
577 views

### How can I plot a radius of all reachable points with pathfinding for a Mob?

I am designing a tactical turn based game. The maps are 2d, but do have varying level-layers and blocking objects/terrain. I'm looking for an algorithm for pathfinding which will allow me to show an ...
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 ...
2k views

### How to create a thread in XNA for pathfinding?

I am trying to create a separate thread for my enemy's A* pathfinder which will give me a list of points to get to the player. I have placed the thread in the update method of my enemy. However this ...
926 views

### How to create a curve from a set of points that passes through said points?

What is the best way to create a smooth curve path from a set of points? For example: I've seen Bezier curves before, but those try to smooth out the path from the set of points, like this:
811 views

### Group arrival steering

I've got group movement implemented pretty much like this: http://www.red3d.com/cwr/steer/CrowdPath.html Basically, that's combining path following and separation. It works nicely as long as units ...
279 views

### Is finding graph minors without single node pinch points possible?

Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up ...
485 views

### XNA RTS A* pathfinding issues

I'm starting to develop an RTS game using the XNA framework in C# and am still in the very early prototyping stage. I'm working on the basics. I've got unit selection down and am currently working on ...
797 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 (...