2D平铺地图的寻路，用于多个目标 [英] Pathfinding for 2D tile map for multiple goals

问题描述

我想在C ++中创建一个简单的基于网格的游戏。寻路是必要的一部分。我一直在寻找，但没有我正在寻找的。

I'm trying to create a simple grid-based game in C++. The pathfinding is necessary part of it. I've been searching, but there isn't what I am exactly looking for.

规则很简单。有一张地图。尺寸通常不超过100×100个砖。 1是地砖，0是墙壁。不允许对角线运动，因此每个网格只有4个方向。然而，大多有一个以上的目标。我想找到最近的路。记住，我们不能只计算，哪一个是最近的距离公式。较短距离的目标可以有更长的路，因为墙。我认为对每个目标使用已知的算法和重复是不是一个好主意，因为它会减慢。

The rules are simple. There is a map. The size generally doesn't exceed 100 x 100 tiles. 1 is a floor tile, 0 is a wall. Diagonal movement isn't allowed, so there are only 4 directions from each grid. However there are mostly more than one goal. I'd like to find the way to nearest one. Remember that we can't just calculate, which one is the nearest by distance formula. The goal with shorter distance can has longer way, because of walls. I think using one of known algorithms and repeating, for each goal isn't a good idea, because it will slow.

你的意见是什么？我应该怎么办？

What's your opinion? What should I do?

推荐答案

这不是一个大问题。为所有真实目标添加距离为1的假设结束节点E，并搜索到达最佳路径E.路径上的最后一个节点将是这些真实目标之一。

This isn't a big problem. Add a hypothetical end node E with distance 1 to all real goals, and search the best path to E. The one-but-last node on the path will be one of those real goals.

这篇关于2D平铺地图的寻路，用于多个目标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！