“Frogger”游戏的算法

Question

这是一个面试问题。设计一个算法来玩“青蛙过河(Frogger)”游戏。你需要引导一只青蛙穿过繁忙的道路。青蛙可以向前/后和左/右移动，而汽车只能向左行驶，青蛙和汽车都只能一次移动一个位置。

我想知道如何将其简化为某些基本的、众所周知的算法。如果在游戏中没有“时间”的概念，我会构建一个安全位置的图，并找到通向青蛙目的地的路径。然而，我不能使用这种方法。

如何将“Frogger”简化为一个众所周知的问题？

- Michael

---

由于所有车辆每个时间间隔都只能移动一个街区，因此您可以构建一个游戏树来涵盖所有可能的情况，并进行搜索，假设每个时间间隔右侧的每个图块上都会出现一辆车。这是一个明显的起点，我很想知道您可以应用什么样的优化。 - user684934

Answer 1

我猜这样一个简单的形式应该能够起作用。（假设这是关于如何运行游戏的说明，而不是如何解决游戏问题）

1) build array to store all tiles on map (each segment of road / water / log)
2) build list to store car / log locations
3) Set up a timer
4) on timer tick, update array of locations with full/empty tiles for each car / log in list (2)
5) check whether the current locaiton of the frog is in the same location as a log / car
6) repeat 4/5 while frog can move

像这样的东西？

- WraithNath

Answer 2

假设汽车和青蛙都是离散移动的，每次只能移动一个“方格”，我们用V表示青蛙垂直（横穿马路）移动的次数，用H表示青蛙水平（沿着车道）移动的次数。如果有5条车道，编号为1-5，则青蛙可以在时刻T=X + 2*V + H位于X车道上。到目前为止，一切都很好。

由于每个车道上的车辆在时刻T的状态是确定的，我们可以生成未来一段时间内整个道路的状态：L(1,T)L(2,T)...L(5,T)。我建议您生成形式为L(1,1 + 2*V + H)L(2,2 + 2*V + H)...L(5,5 + 2*V + H)的虚构道路状态，并寻找一种状态，在该状态下您可以看到通向另一侧的开放直线，从而消除时间因素。

实际上，您正在进行暴力搜索，但是如果车道数量和允许的移动次数合理，那么没有理由不这样做。

- staafl