问题描述
只是为了提高自己的Java脚本的技能，我试图建立一个吃豆子游戏的JS。由20具有20的网格。这个网格具有0和1的这表明，如果有一个壁或路径。现在，我想开发一个算法中的恶魔跟着吃豆子。我不知道哪种算法，我应该去。
于是我输入功能将FOO（当前位置，吃豆子位置，电网，路）
VAR迷宫= [[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0 ，0,0,0]
[0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0]
[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
[0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0]
[0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0]
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0]
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]
[0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,0]
[0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0]
[0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0]
[1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1]
[0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,1,0]
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0]
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0]
[0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0]
[0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0]
[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
[0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0]
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]];
有关加权图你有几个选项查找最短路径：
- BFS - 最简单的解决方案 - BFS完成和最佳的 - 它会找到最短路径，如果这样的存在
- 双向BFS - 基本上是相同的，但千万当两个BFS满足从两侧BFS，并结束。它显著降低发现的顶点数目。我解释了更多关于如何做到这一点，为什么它是很好的这个线程。
- 启发式的 A *算法 - 这是一个明智的算法，因而通常更快然后其他人，但是很难编程。请使用受理的启发函数有了它，像的的。
个人 - 我想我会使用BFS在这种情况下 - 但吃豆子开始，直到你发现所有的目标（恶魔位置） - 它会给你从每个妖吃豆子的最短路径。
请注意，如果你只有几恶魔和一个大板，做A *数次（每妖一次）可能是一个更好的解决方案。
每个人都应该大概基准它，看看它实际上是更好的。
Just to enhance my java script skills i am trying to develop a pacman game in js. have a grid of 20 by 20 . This grid has 0's and 1's which indicate if there is a wall or a path . Now I want to develop a algo for the demons to follow the pacman . I am not sure which algorithm should I go for .
So my input to the function will be foo( current position, pacman position,grid, path)
var maze = [ [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
[0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
[0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
[0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
[0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,0],
[0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0],
[0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0],
[1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1],
[0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,1,0],
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
[0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
[0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
[0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
[0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]];
For unweighted graph you have a several options for finding a shortest path:
- BFS - simplest solution - the BFS is complete and optimal - it will find the shortest path if such exist.
- Bi-Directional BFS - basically the same, but do BFS from both sides, and end when two BFS meet. It significantly decreases the number of vertices discovered. I explained more about how to do it and why it's good in this thread.
- Heuristical A* Algorithm - it is an informed algorithm, and thus usually faster then the others, but is harder to program. Use an admissible heuristic function with it, like the manhattan distances.
Personally - I think I'd use BFS in this case - but start from pacman, until you discover all "targets" (demon locations) - it will give you the shortest path from each demon to pacman.
Note that if you have just a few demons and a big board, doing A* several times (once per demon) might be a better solution.
One should probably benchmark it to see which is actually better.
这篇关于算法中加权图最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！