1

前段时间我问了一个关于java 2d pathfinding的问题... Pathfinding 2D Java game？

我正在开发的游戏是基于主题医院的想法。从我的问题中选择的答案，A* 寻路，链接很棒，非常有帮助。我最终将把它应用到我的游戏中，但是我还有一些关于它的问题/问题。

在我的游戏中，地图会改变。本教程假设地图是静态的（我认为）。我一直在看代码，据我所知，我只需要创建一个方法来调用来更新寻路代码中的游戏地图。

其次，我看到了 GameMap 类。我有自己的班级，叫做 Board，里面有所有的瓷砖。我相信我可以将 GameMap 上的方法集成到我的 Board 类中。正确的？

第三，我一直在研究任何房间都将被视为阻塞的推理。我的意思是，房间覆盖的任何方格都被算作阻塞。我在想人们会从哪里进入房间。然后，他们将不得不在这些房间周围移动才能到达不同的地方。我在想我会为每个正方形反转 Blocked 布尔值，但这有两个原因是行不通的。1，房间可能有相邻的墙壁，并且可能会破坏寻路。2、如果阻塞状态只是简单的倒置，那么房间内的任何实心物品倒置后都会被视为不实心，这可能会在它们与墙壁接触时出现问题。

想一想，如果您可以将正方形的边制作成块状而不是实际的整个正方形会更好。这一定是可能的，但我只是通过使用上一个问题中的教程获得，并且不确定我是否应该尝试更改 A* 来执行此操作，或者解决房间物品问题的解决方法。

对这些问题有什么想法或建议吗？我今天正在实施简单的路径查找，但只是提前思考。

4

3 回答 3

1

From a quick look, it looks like the isValidLocation(mover,sx,sy,xp,yp) method defines if moving from point(sx,sy) to point(xp,yp) is a valid move.

If this method took into consideration the direction of the move, you could block specific directions out of / into a block without making the block entirely impenetrable. This way, you could have 2 accessible blocks next to each other with a solid boundary between them.

This approach has some interesting side-effects such as the ability to create one-way boundaries (block A has access to block B, but not vice versa.) Could be a useful game mechanic in letting the A* take one way doors (fire escapes?) into account.

There is an algorithm called Adaptive A* which can recalculate a portion of a path say, if someone stands in front of you. I would concentrate on the vanilla A* first, you could always calculate a new path from that point on if you found half way through that a previously valid path was blocked.

This looks like interesting reading: Real-Time Adaptive A* [PDF]

于 2009-07-02T11:06:49.807 回答
0

If the game map changes you do need to recalculate paths, however you don't necessarily need to recalculate all paths depending on what changed.

You should integrate the methods of GameMap into your Board class (with modifications to the GameMap class).

To block sides of a square you could think of each tile as nine separate ones instead (3X3). For example for a tile with blocked horizontal walls, instead of a single square you can represent the tile (to your a* algorithm) as:

[X| |X]
[X| |X]
[X| |X]

A tile with a vertical and horizontal tile blocked:

[ | |X]
[ | |X]
[X|X|X]

You would have to store the additional edge information with your game map. Hope this helps.

于 2009-07-02T10:58:41.023 回答
0

对于路径问题：

一个简单的解决方案是，当且仅当当前路径中的下一步移动被认为是无效的（地图上已放置新元素、添加了新房间、已移动门......）时，才重新计算路径. 当然，您从当前位置重新计算。如果阻塞元件是另一个移动元件，问题就更复杂了。在这种情况下，两个对象之一必须等待几个周期，另一个必须重新路径，具体取决于优先级。但是，这可能会导致多路径碰撞的问题（门的一侧各有两个高优先级对象，门内有一个低优先级对象：它不能移动，高优先级会等待很长时间）

对于房间问题：

通常将房间定义为一组瓷砖而不是一个瓷砖。因此，您可以为一个房间定义子图块是可以通过的，而那些不是。如果您的模型允许，您甚至可以描述存在于不同瓷砖中的物体并将它们设置为不可通行：等候室（6 瓷砖 x 4 瓷砖房间）如果完全可以通过，但包含一组椅子和一个小使某些 subtiles 无法通行的喷泉。

希望这可以帮助

纪尧姆

于 2009-07-02T11:28:59.853 回答