Tagged Questions

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

48 views

How do I handle objects with a width and height in grid-based pathfinding?

I'm using the Jumper library for Love2D to do grid-based pathfinding, which worked fine until I wanted to make larger enemies (with larger collision boxes). How do i do that? My initial idea was to ...
360 views

Aligning pathfinding to the center of tiles?

I'm looking to achieve tile by tile movement in a project I'm working on. I employed the use of the asset Simply A* Path-finding to allow a unit to navigate the terrain. Since the tiles are ...
187 views

Graph search with a high number of actions

I have implemented A* to reach a goal state from a start state. My state is position X,Y, angle and others state variable. I have a number of actions. What I call actions is : A* on a grid has 4/8 ...
307 views

How to choose and scale heuristics for A-star on a graph?

I am trying to find the best and scale my cost function for my algorithm. I am following amit blog which explain that (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-...
467 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS -(void)callDfs:(int)...
13 views

View the path a AI is walking along in Unreal Engine 4

I'm using unreal engine 4.12.4 and I want to be able to see the path that an actor will use when i trigger "Simple Move To Location" and i want to see the path as a line in game for testing.
79 views

Doubts on player movement strategy

What I want to achieve is the player moving to the touched position on a 2D grid-based game, stopping at the last reachable spot if the target position is unreachable. What is the strategy usually ...
40 views

What's an optimal procedure to create a connected cyclic grid of nodes and edges for A* pathfinding

like the title says, I'm trying to create a grid of nodes that hold edges or connections to each other so I can perform A* algorithm to have objects traverse across them as seen in your standard RTS. ...
61 views

How to implement A* pathfinding for enemies to follow player

The enemies in my game are supposed to follow the player in order to cause damage to it. Right now I have it where the enemy just goes in the direction that will bring it closer to the player, and ...
18 views

UE4 Navmesh precision

I'm trying to make my very tiny man pathfind his way through a map of a school but the navmash won't recognize some of the hallways cause they are very narrow like this. So as you can see the man ...
49 views

Multilevel 2D grid graph and A*

I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill. ...
102 views

Pathfinding on multiple grids connected through teleports

I try to create a "AI" that can move independently on a map structure where the individual maps are only connected by one directional teleport squares (links). There are some map areas you can only ...
250 views

Local avoidance together with any-angle types of A* Pathfinding

Recently I have been implementing the Block A* any-angle path-finding algorithm in a project I have, for which I need extremely efficient results due to the large number of NPCs. However, I still do ...
83 views

Using my pathfinding more efficiently

I'm making a roguelike in C# with the Roguesharp libraries, in which the map can be as large as 200x200 cells. When I have an entity requiring pathfinding, I am using Roguesharp's built in pathfinding ...
239 views

How to get NPC to Find and Follow Path to other NPC?

Problem: I am using Skyrim Creation Kit to create a very simple mod. I want the mod to make one NPC follow another NPC. My first problem is that I am not really 100% sure where to start. The second ...
247 views

C++ A Star Algorithm [path takes wrong route] using <deque> & unique_ptr

I am having issues, trying to get my A Star algorithm working, the main problem is with my process of the algorithm, I am using something known as the TL engine which has some of its own datatypes and ...
115 views

Object outlining

I have an object whose boundaries can be define using a convex collider. I have an AI which needs to outline that structure to patrol it. The object is dynamic and composed of pieces like LEGO, each ...
80 views

How to avoid 2d enemy using trigonometry?

I'm making a game in Javascript & HTML5. I have a "bullet" (let's call it so) that needs to reach the enemy (at fixed position) and that need to avoid the enemy's "bullet". To make the bullet ...
142 views

GameMaker : how can i get the instance ID of multiple instance in a radius?

GameMaker and coding noob here, need help on something maybe trivial for some of you. I'm working on the map part of a game. I have a map with spots on it, each spot is an instance of the same object....
191 views

How do I calculate paths for objects with limited acceleration?

For example, say I have a car and a car has a specific minimum turning radius and I want to drive that car from point a to point b, but the car isn't facing point b. How do I compute a path to point ...
32 views

AI: Turn-Based Movement with 2 actions per Unit

I am currently building a turnbased tactics game. The Board is a small (about 4*6) tiled grid. The AI plans all moves of its units, each unit can move 2 times move and attack or attack at ...
200 views

Pathfinding over a moving platform

I have beens struggling with the following. In the game I am developing with Unity 5 in C#, I need to implement basic pathfinding over moving platforms (not with moving platforms). It means, I am not ...
1k views

Game Maker: Studio - Make objects avoid other instances of same object with A* pathfinding

I have a game where there are multiple enemies who must chase a single player. I have pathfinding set up using the GML A* pathfinding with mp_grid and a path. However, these enemies can walk on top ...
102 views

How can I remove unnecessary nodes from my path?

How do I remove the unnecessary nodes from the path to make it as short as possible? Idealy I'd like the result path to look like the green line. The red thingy is not walkable. var ...
44 views

How can I make cars drive navigate an intersection without colliding?

I'm trying to create a 2D game with a traffic intersection: My car game-objects need to pass through the intersection without colliding with each other, and without stopping, if possible. How can ...
20k views

What path finding algorithms are there? [closed]

I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
627 views

Why is my A* Pathfinding incredibly slow?

I'm trying to use A* to make my enemies move about, but it takes up to 20 seconds to get a path to walk. My grid is only 64*64. This is my code: #include "AStar.h" #include "Node.h" #include "...
168 views

A* pathfinding takes too long, shortcuts needed

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* path-finding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 ...
48 views

Circular fighter motion algorithm

Is there an algorithm to make ships take semi-circular patterns? I need something like the below image: Big Blue- Command Ship Small blues - fighters Red lines - path of movement I want the ...
72 views

Locust Swarm algorithm for path finding (devour and move on)

I need to model a locust swarm that devour food stacks and move on to next stacks. I searched for articles and found few articles. These papers is about optimization applications but I want to convert ...
273 views

Code sample on how to implement Lee's visibility graph

In my recent search, I've been amazed about how difficult it is to find code examples or information on how to build visibility graphs. Considering its importance on video-game development for AI path-...
102 views

Pathfinding to unknown destination point

Usually you need path finding algorithms to find one or the best path between two points. Do you know if path finding algorithm where you don't know the destination point exists? I have a graph made ...
42 views

Movement looks funny If player takes up multiple tiles in tile-based game

So here is my problem: Start = +++ +++ +++ End = --- --- --- Player = *** *** *** +++000000000000 +++000000000000 +++000000000000 000000000000000 ...
33 views

How do I turn a vector map into a nav mesh?

I have the following path finding problem: I have a map that is described as a set of polygons that are traversable and need to somehow write path finding for the system. The current data is that the ...
33 views

Following waypoints, condition is never fulfilled

Given a 2D-grid which is defined like below and is used to draw a grid consisting of cells: int[,] grid; //filled with 0 (blocked) and 1 (walkable); I also have a A*-algorithm implemented which ...
138 views

Funnel algorithm

I'm implementing the funnel algorithm for pathfinding. After searching many resources I found those : https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf http://digestingduck.blogspot.com.by/2010/03/...
174 views

How can I adapt A* pathfinding to work with platformers?

I have an A* implementation that works in "top down" situations where gravity is not taken into account for pathfinding. But, I am looking to modify to work in a 2d platformer situation. I am using ...
72 views

Should I use the pathfinding client side or server side? [closed]

I'm developping a game where the user can walk in a room (with the others players). There are some obstacles that blocks the user. I'm using a Javascript pathfinding library to find where the user can ...
103 views

Dijkstra's Algorithm - Infinite loop

While running Dijkstra's Algorithm to assign a direction to every tile and when an object land on the tile, follow the direction to a goal. I encountered an infinite loop (or I think it is). The ...
81 views

An algorithm for forming unit groups

Currently in my game engine when a user selects a large number of units and commands them to a target each unit finds its own path using Jump Point Search. The performance of this is generally OK. ...
79 views

Forward A-star pathfinding vs Reverse A-star pathfinding

Under what condition does doing Forward path finding or Reverse pathfinding get better result? Most tutorials for open grid tower defence games says to pathfind from the Goal to the monster. Why is it ...
1k views

How can I generate a (relatively) linear dungeon path?

We developing a concept for an action side-scroller. What we need is a way to generate a (relatively) straight map. By this I mean something like... It's clear to see that this map follows one ...
319 views

Is it possible to use nav-mesh in 2d game in Unity?

I'm working on game that needs navigation and obstacle avoidance. I've used nav-mesh on 3d project before but now I'm trying to use it in 2d sprite game but it seems like it doesn't work. I want to ...
90 views

Enemy shake/vibrate when following character

I am using the arongranberg A* path finding project to create way points for one enemy to follow the player. However, the enemy vibrates back and forward by about 0.1 - 0.2 unit distance when moving. ...
39 views

HPA* on weighed (non-uniform) 2D grid maps

I'm researching pathfinding algorithms on the 2D grid maps in regard to their performance/memory consumtion. I'm particulary interested in the weighed maps as something much close to the reality than ...
249 views

What is best method for 2D pathfinding in procedural world?

I have been researching path-finding for 2D games and would like to create a system that allows A* to perform as best as possible over a near infinite world. This system is intended to manage not only ...
29 views

Automata Editor

I'm currently developing a State machine editor as a tool for some games my team is developing: but the algorithm I chose to display the paths between the states doesn't care about the obstacles, ...
69 views

How can I implement A* so that it accounts for the size of the actor?

I'm trying to make a little A* implementation using polygon verticies as nodes instead of grids and I ran into the problem of figuring out what paths are wide enough to accommodate the actor moving ...