Tagged Questions

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
1answer
140 views

Pathfinding results in false path costs that are too high

I'm trying to implement pathfinding in a game I'm programming using this method. I'm implementing it with recursion but some of the values after the immediate circle of tiles around the player are ...
5
votes
1answer
194 views

A* search in hexagonal grid with minimum turn radius

I need to run an A* search through a hexagonal grid. However, I have one nasty constraint: my vehicle can only turn so sharp. It has a specified minimum turn radius. I can't quite see how to translate ...
-1
votes
1answer
156 views

How to speed up AStar? [closed]

I have this AStar class, and at the movement it is INCREDIBLY slow. It takes waaay longer than I expected it too, and I'm not quite sure why. I added the generation part at the very beginning to ...
2
votes
3answers
984 views

Map building - Tower Defense

Before diving too deep into my question, let it be known that I am learning as far as java script goes and figured a simple Tower Defense game would be an excellent way to learn things. So I have ...
23
votes
4answers
2k views

Is the Manhattan distance monotonic when used as heuristic function?

I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1. I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
-1
votes
3answers
313 views

Looking for detailed pathfinding examples

I am currently working on a 2D-TopDown game. Now I was looking for pathfinding algorithms. I read and understood A* and Dijkstra. But there are still some questions I have. So I am looking for ...
1
vote
1answer
199 views

Quick 3D sight calculation algorithm

I have a tile based board game where units move in 3D space on a 2D isometric view. When calculating attack tiles for a unit, how do I verify that they aren't shooting through a wall or a level too ...
-1
votes
1answer
209 views

A* Search in games [closed]

I am making car racing game. I stuck with the AI of the game. I go through with the A* search, but there is problem that I want to ask that whether we have to make a 2D array and than apply search on ...
4
votes
1answer
371 views

Path finding in games

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;) So, i've done a little bit of searching ...
3
votes
1answer
141 views

How to create a path-finding compatible road map from user input?

I'm currently working on an agent simulation (inspired by the recent SimCity release). Now, basically I understood how agents work but I do not understand how to put them into context. Agents travel ...
1
vote
2answers
571 views

Displaying possible movement tiles

What's the fastest way to highlight all possible movement tiles for a player on a square grid? Players can only move up, down, left, right. Tiles can cost more than one movement, multiple levels are ...
0
votes
0answers
50 views

How to modify graph ingame?

The pathfinding in my game uses this function to generate a graph: def make_graph(self, size, impassable): nodes = [[astar_gridnode(x, y) for y in range(size)] for x in range(size)] graph = ...
13
votes
2answers
814 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 ...
1
vote
2answers
543 views

A* path finding for road network - data structure to represent directivity

I have been reading A* path finding to apply on a road like network structure. Most of the code I saw is about A* on tile based maps. There is a short description at Amit's page here about what I am ...
4
votes
1answer
353 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
395 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 ...
-1
votes
1answer
431 views

Ways to achieve path finding on android [closed]

I have spent two weeks on this task and its to no avail,i hope your expertise can help me. I want to create a simple set of activities that allow the shortest path to be calculated between two points ...
2
votes
1answer
223 views

How to predict future location of a Car in a Navigation Mesh based pathfinding system?

I am developing a car based shooting game in which the Cars have to shoot each other 3/4 times and eliminate it from the game. I am trying to develop the AI for my cars now. The problem is how can I ...
11
votes
1answer
1k views

Pathfinding on a uneven planetary surface

My question is what would be the best approach to pathfinding on an uneven planetary surface? Background Information I have created a planet from displacement mapping 6 sphere projected planes. ...
7
votes
1answer
290 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. ...
3
votes
1answer
211 views

How can I find all shortest paths using A*?

It is possible for A* Path Finding to return all the shortest paths given a graph/map? For example, given the map below: ----------- --a--X--b-- ----------- The said map can return four (4) ...
0
votes
1answer
536 views

Pathfinding with different sized units [duplicate]

I am actually working on a general purpose pathfinding library (find it here), mostly oriented for grid-based maps. I was looking for ways to integrate support for pathfinding with units of different ...
0
votes
1answer
100 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 ...
3
votes
2answers
326 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 ...
2
votes
1answer
164 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 ...
1
vote
2answers
426 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 ...
1
vote
1answer
139 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 ...
1
vote
2answers
474 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 ...
1
vote
2answers
268 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 ...
11
votes
3answers
865 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 ...
1
vote
1answer
155 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 ...
1
vote
2answers
1k 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 ...
5
votes
1answer
239 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 ...
2
votes
1answer
347 views

World-map navigation and path-finding

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 ...
5
votes
3answers
771 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 ...
3
votes
1answer
188 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 ...
0
votes
1answer
1k 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 ...
1
vote
1answer
116 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 ...
-2
votes
1answer
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 ...
3
votes
2answers
211 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 ...
9
votes
2answers
399 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 ...
4
votes
1answer
327 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 ...
-5
votes
2answers
559 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 ...
14
votes
6answers
1k 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 ...
3
votes
2answers
455 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 ...
3
votes
4answers
1k 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 ...
3
votes
3answers
177 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. ...
6
votes
1answer
162 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 ...
2
votes
1answer
109 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 ...
2
votes
1answer
362 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 ...