lab-jump-point-search

KO | EN

gitlite — search

#javascript #react #llm #golang #go #android #rust #linux #docker #awesome #cli #awesome-list #vue #security

lab-jump-point-search

(★ 13)

Lab "Efficient Algorithms for Selected Problems" in summer term 2016 for University of Bonn

lab-jump-point-search 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Lab Project: Efficient Algorithms for Selected Problems

This reposity stores the work for the Lab Projct: Efficient Algorithms for Selected Problems in summer term 2016 for University of Bonn.

We implemented and visualized the algorithm Jump Point Search. This algorithm is used for finding the shortest path in grid graphs.
The algorithm was presented first by Harabor and Grastien in papers "Online Graph Pruning for Pathfinding on Grid Maps" and "Improving Jump Point Search".
Further we implemented improvements to the algorithm, namely bouding boxes, by S. Rabin and N. Sturtevant by paper "Combining Bounding Boxes and JPS to Prune Grid Pathfinding".

The Java applet can be downloaded at [releases](https://github.com/drademacher/lab-jump-point-search/releases/latest). The applet visualizes the algorithm and is aimed to help understanding the algorithm behavior on various examples. These examples can be generated by random map generation or loading a map file from the repository. Any example can be modified to see how the algorithm reacts at different scenarios.

![GUI](https://raw.githubusercontent.com/drademacher/lab-jump-point-search/master/report/figures/javafx.png)

## Benchmarks

The algorithms which were compared in the benchmarks are the well-known [A*](https://en.wikipedia.org/wiki/A*_search_algorithm), Jump Point Serach (JPS), the improved version of Jump Point Search (JPSplus). At some maps we improved the runtime by using bounding boxes to prune the exanding possibilities. When the usage of bounding boxes was so small because of the map size, we omitted those benchmarks.

The benchmark map files can be found at the freely available pathfinding
library [Hierarchical Open Graph](https://github.com/nathansttt/hog2/tree/master/scenarios). The benchmarks show that our implementation of Jump Point Search clearly dominates A* in run time.

**Runtime on random maps:**

![Random Maps](https://raw.githubusercontent.com/drademacher/lab-jump-point-search/master/report/figures/02_time_random.png)

**Runtime on Baldurs Gate maps:**

![Baldurs Gate](https://raw.githubusercontent.com/drademacher/lab-jump-point-search/master/report/figures/03_time_bg512.png)

**Runtime on Dragon Age maps:**

![Runtime on Dragon Age maps.](https://raw.githubusercontent.com/drademacher/lab-jump-point-search/master/report/figures/04_time_da2.png)

**Runtime on StarCraft maps:**

![Runtime on StarCraft maps.](https://raw.githubusercontent.com/drademacher/lab-jump-point-search/master/report/figures/05_time_sc1.png)

lab-jump-point-search

lab-jump-point-search 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

lab-jump-point-search

lab-jump-point-search 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README