我正在开发一个游戏，玩家可以在任意方向移动地图由放置在任意位置和不同大小的障碍物组成。所有障碍物/物体均为矩形。
到目前为止，我已经实现了一个基本的a*算法（8个移动方向），使用简单的二维网格，其中网格中的每个单元格都指向地图上的单个像素。显然，它不太好用，尤其是在20000x2000左右的大型地图上。
请注意，由于一些外部约束，我不能使用二维网格以外的数据结构。
在我跳进JPS，沼泽和其他花哨的东西之前。我想我应该尝试一种不同的方法把地图分割成运动点。也就是说，不是1个单元格1个像素的映射，而是1个单元格5x5像素宽的区域。
不过，我似乎找不到合适的方法来做这件事。由于球员的大小可以改变，由于任意设置障碍，我遇到了各种各样的清除问题。
所以我的问题是：如何在给定上述约束的情况下，有效地将地图分割成二维网格供a*使用？
最佳答案
你可以在地图上创建一个NavMesh，比如说人工智能游戏编程智慧——在谷歌图书上也有很大一部分（比如谷歌的“构造NavMesh”）。
另一个选择（如果不想限制自己使用navmesh）是使用类似四叉树导航的方法。