C#路径查找A +性能问题 [英] C# path finding A+ performance problem
问题描述
嗨！
我正在XNA游戏工作室中编写游戏，
这是一款2D游戏，其中AI需要某种类型的路径查找功能.我选择使用Dijkstra的算法，除了目标位于地图的相反部分外，它似乎工作得很好.然后，我遇到了一些严重的性能问题，可能要花一分钟甚至更长时间. (A +表示您可以向四个方向行驶，而不像十字A *.)我想这是瓶颈所在的优先队列，但我不确定.
我使用的优先级队列可以在以下位置找到:
http://blogs.msdn.com/b/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx [
继承接口IPathSquare的所有"gameObjects"都可以判断该位置是否可行走/自由.
这是界面.
Hi!
I am writing a game in XNA game studio,
it''s a 2d game where the AI needs some type of path finding. I have choose to use Dijkstra''s algorithm and it seems to work very good, except when the goal is at the opposite part of the map. Then I get some serious performance problem and it can take up to a minute or even worse. (A+ means that you can go in four directions and not like a cross A*.) I guess it''s the priority queue that is the bottle neck but I don''t know for sure.
The priority queue I use can be find at:
http://blogs.msdn.com/b/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx[^]
The map consist of a multi array which have some ''gameObjects'' in it.
All ''gameObjects'' inheriting the interface IPathSquare which can tell if the position is walkable/free.
Here''s the interface.
namespace PathLib
{
interface IPathSquere
{
bool isFree();
}
}
这是路径查找代码，请注意PriorityQueue来自上面的链接.
Here''s the path finding code, note that the PriorityQueue comes from the link above.
namespace PathLib
{
class PathFinding
{
private IPathSquere[,] map;
public Point[] findPath(Point start, Point finish)
{
// are the points within the map's bounds
if (!isInMap(start) || !isInMap(finish))
return null;
// create priority queue
PriorityQueue<int, LinkedList<Point>> pq =
new PriorityQueue<int, LinkedList<Point>>();
// setup a init list
LinkedList<Point> lst = new LinkedList<Point>();
lst.AddLast(start);
pq.Enqueue(1, lst); // the priority value doesn't really matter here
// find path, loop while 'pq' isn't empty
while (!pq.IsEmpty)
{
lst = pq.Dequeue(); // get top of priority queue
Point curPos = lst.Last.Value;
if(curPos.Equals(finish)) // finish position?
return lst.ToArray<Point>(); // return the path as an array
// add new nodes
Point[] temp = { new Point(curPos.X-1, curPos.Y), // left
new Point(curPos.X+1, curPos.Y), // right
new Point(curPos.X, curPos.Y-1), // down
new Point(curPos.X, curPos.Y+1) // up
};
// check that they are within the map's bounds and free
foreach (Point p in temp)
{
if(isInMap(p) && // within the map's bounds
map[p.X,p.Y].isFree() && // free position in map
!lst.Contains(p)) // visited before (if so, then throw p)
{
// copy constructor
LinkedList<Point> tLst = new LinkedList<Point>(lst);
tLst.AddLast(p); // add our new point to the path
pq.Enqueue(tLst.Count, tLst); // add to 'pq' queue
}
}
}
return null; // no path found ...
}
public IPathSquere[,] Map
{
set { map = value; }
}
//help functions
private bool isInMap(Point pos)
{
int rows = map.GetLength(0);
int cols = map.GetLength(1);
return 0 <= pos.X && pos.X < cols
&& 0 <= pos.Y && pos.Y < rows;
}
}
}
也许我应该提一下，如果有许多可步行/可自由行走的区域，则延迟会变得非常沉重，例如20 * 15正方形的地图.因此有可能获得更好的性能(是的.)，我该如何实现.
在此先感谢////WaZoX
Maybe I should mention that the lag starts to be very heavy with a map like 20*15 squares if there is many walkable/free. So is it possible to get better performance (yes it must be..) and how can I achieve that.
Thanks in advance // WaZoX
推荐答案
从性能的角度来看，我发现其中有些非常糟糕的事情.其中一个正在使用Contains(尤其是在链表上)，另一个正在创建潜在大型结构的副本(再次是链表，因此需要大量的指针追踪).创建大量临时数组也不是一件好事.
我已经在性能设置中实现了A *两次，它与A +并没有太大区别..
所以我要说说我在那里做的事.
我不得不问，当您找到一个已经处理过的节点时，您无需检查新路径是否比旧路径短.那是正确的行为吗?在A *中不会，
无论如何，我实现了带有可减小键的最小堆(因此，当找到到打开"列表中的节点的较短路径时，不必删除和重新插入它，可以对其进行更新，这在实践中会更快)，而对于封闭列表，则是半稀疏网格"(因为地图有点大)，它只是一个由32x32布尔"(以uint数组实现)的块组成的网格，这些块仅在需要(当向他们写了一个真实的时候).然后，测试节点是否在关闭列表中为O(1).我还使用了另一个半稀疏网格"来从O(1)而不是通常的O(n)中的打开列表中查找节点.
总的来说，我花了很多时间在相当大的内存空间中进行交易，并且效果很好.
另外，该路径不是累积"的，将存储父"路径，最后将追溯到该路径.
我希望其中一些可以帮助您.
I see a couple of things in there that are very bad from a performance perspective. One of them is using Contains (especially on a linked list), the other is creating a copy of a potentially large structure (a linked list again, so lots of pointer chasing). Creating lots of temporary array''s isn''t great either.
I''ve implemented A* a couple of times, in performance settings, it shouldn''t be that much different than A+..
So I''m going to say what I did there.
I have to ask though, when you find a node that you already handled, you don''t check whether the new path is shorter than the old one. Is that correct behaviour? In A* it wouldn''t be,
Anyway, I implemented a min-heap with decreasable-keys (so when a shorter path is found to a node that is already in the Open list, it doesn''t have to be removed&reinserted, it can be updated which is faster in practice), and for the closed list a "semi sparse grid" (because the maps were a bit big) it was just a grid of blocks of 32x32 "bools" (implemented as an array of uints), the blocks would only be present when needed (when a true is written to them). Testing whether a node is in the closed list is then O(1). I also used yet an other "semi sparse grid" to look up nodes from the open-list in O(1) instead of the usual O(n).
In all, I traded in quite some memory space for a lot of time, and it worked out rather well.
Also, the path was not "build up", the "parent" would be stored and at the end the path would be traced back.
I hope some of that can help you.
这篇关于C#路径查找A +性能问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
