Code Monkey home page Code Monkey logo

jpspluswithgoalbounding's Introduction

JPSPlusWithGoalBounding

JPS+ with Goal Bounding

This project implements 2D grid pathfinding using JPS+ with Goal Bounding. JPS+ is an optimized preprocessed version of the Jump Point Search pathfinding algorithm. Goal Bounding is a node pruning pathfinding technique.

The Goal Bounding concept was first conceived by Steve Rabin in Jan 2015 and was first unveiled to the public in the GDC AI Summit lecture "JPS+: Over 100x Faster than A*" in San Francisco on March 2015. This presentation can be viewed at www.gdcvault.com and the PowerPoint slides are part of this project.

Goal Bounding is a node pruning technique that greatly speeds up pathfinding. Goal Bounding is the concept of computing and storing an axis-aligned bounding box for each node edge that contains all nodes that are optimally reachable via that edge. During runtime, any edge (neighboring node) will only be explored if the goal node is contained in the axis-aligned bounding box for that edge. Goal Bounding can be applied to any search space (grid, graph, NavMesh, etc.) using any search algorithm (Dijkstra, A*, JPS+, etc.) and the search space can be unidirectional and have non-uniform costs between nodes. The compromise with using Goal Bounding is that the Goal Bounding data must be preprocessed offline taking O(n^2) time, thus making it not feasible to support dynamic runtime modifications of the search space (adding or removing edges/walls). Goal Bounding requires linear storage of data, O(n), with respect to the search space (typically 4 values per node edge, with a grid representation having 8 edges per node, for a total of 32 values per node).

JPS+ was independently invented by Steve Rabin one month before it was unveiled by Harabor and Grastien at ICAPS in June 2014. A description of JPS+ can be found in the book Game AI Pro 2, published by CRC Press (April 2015). JPS+ is an optimized preprocessed version of Jump Point Search. JPS+ is a node pruning technique, like Goal Bounding, but both techniques are orthogonal to each other as they prune nodes in unrelated, but complementary, ways. JPS+ only works on grid search spaces with uniform cost. Because of the preprocessing of JPS+, the search space cannot be easily updated at runtime (adding or removing edges/walls). JPS+ requires O(n) precomputation and storage linear in the number of nodes, O(n), consisting of 1 value per node edge (8 values per grid node).

This project is highly optimized and designed to be entered into the Grid-Based Path Planning Competition (movingai.com). The project will open up maps (.map files) in the Maps directory, preprocess them if necessary (creating files ending in .map.pre), and then run pathfinding tests on them (.map.scen files). You can download map files (.map) and scenario files (.scen) from movingai.com (maps from Dragon Age Origins, StarCraft, WarCraft III, Balders Gate 2, and more).

List of optimizations applied to this project:

  • JPS+ algorithm
  • Goal Bounding algorithm
  • Preprocess optimizations
    • Bucket open list with recycling buckets
    • Function pointer lookup table for parent direction and wall permutation (2048 cases pointing to 48 functions)
  • Runtime optimizations
    • Octile heuristic
    • Fast stack in conjunction with unsorted open list
    • Function pointer lookup table for parent direction and wall permutation (2048 cases pointing to 48 functions)

If you have any questions, comments, or suggestions, please contact Steve Rabin at [email protected].

jpspluswithgoalbounding's People

Contributors

steverabin avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

jpspluswithgoalbounding's Issues

Optimize Reprocessing time

For large map, bigger than 1000x1000 for example, preprocessing is too slow. It will take 1 week to calculate the goal bounding.

I optimized the implementation and it only take 30 minutes now, hope the method helps for who wants to play with big map.

First. just calculate the bounding for jump points instead of all grid and processing time reduced to 1-3% in large map(1000x1000 for example). The search time of JPS almost same as before.

Second optimization is to use normal queue instead of priority queue for Dijkstra flood method, result is same as before. Preprocessing time reduced to 25%.

example bug

primitiveresource.cs should be
`using UnityEngine;
using System.Collections;

public class PrimitiveResource : Resource
{
public float MinScalePercentage = 0.1f;
private Vector3 startingScale;

protected override void Awake ()
{
	base.Awake ();
    startingScale = transform.localScale;
}

public override void RemoveResource(float value)
{
    base.RemoveResource(value);
	transform.localScale = startingScale * (MinScalePercentage + (1f - MinScalePercentage) * (Capacity/startingCapacity)); // scale down based on capacity
}

}`

Out of bounds array access

At https://github.com/SteveRabin/JPSPlusWithGoalBounding/blob/master/JPSPlusGoalBounding/PrecomputeMap.cpp#L502 the m_distantJumpPointMap array seems to be accessed out of bounds:

int jumpDistance = m_distantJumpPointMap[r - 1][c - 1].jumpDistance[UpLeft];

On the first iteration, r and c are 0 and thus the accessed indexes -1 and -1. Maybe I am missing some magic somewhere that would fix this, but this being C++ it might be just luck that these out of bounds values were the desired 0 in tests?

Preprocess

How does the map preprocessing work? i need a complete explanation plz. i want to use this for my game. i understand how it is done, but what exactly maked it be preprocessed?is it because of stdafx.h and does that mean that it compiles normally on first run but the next compiles will not rework the map?

example doesn't work when minion is duplicated

multipleresourcecensor.cs struggles when the minion gets duplicated n times, something to do with the cacheupdatedelays
as I understand it, this variable's purpose is to avoid spamming by multiple agent, like a lock, I suggest moving it to the resource itself and have the lock mechanism as part of resource query, this way, naturally 1000 agents will show politeness towards the trees

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.