Jump to content

  • Log In with Google      Sign In   
  • Create Account


snowmanZOMG

Member Since 29 Aug 2010
Offline Last Active Today, 01:50 AM

Posts I've Made

In Topic: A* polishing - optimising implementation for large map

28 January 2014 - 11:24 AM

Correct me if I am wrong (I am not a C++ programmer), but I don't think you can use a priority queue because you need to update the values.

 

Sure you can.  The STL heap functions don't provide an update function, but you don't exactly need one in the context of A* if you keep enough extra state.  A properly written heap update performs in O(log n) time, but the only way to perform an update using the STL provided functions is to modify the contents directly yourself and then call make_heap() which runs in O(n) time.  This is not desirable.  However, you don't need to do a full heap rebuild; as long as you keep flags to know when a node is opened or closed, you can simply keep throwing on the updated node cost values into your heap and every time you pop off the heap you should check if the node you retrieved is open or not.  If it isn't open, just skip it!

 

This is how I've implemented my A* function.  You may be concerned that you'll have multiple instances of a node in the heap with different costs, but this doesn't actually affect the correctness of the algorithm as long as you have a flag (or some other structure) to determine if the node is in the open list or not.  The heap serves only to keep track of the next min cost node to explore, not to actually tell you if a node is open or not.  And due to the relaxation process of edges inherent in shortest path algorithms, you will always be popping off the most current cost estimates to a node if you have multiple copies.

 

Using a good structure to retrieve the min cost node is critical to good performance in cases where you have a large map to path through, but possibly just as important is the initialization time.  I haven't looked thoroughly at your code but I also suspect your graph initialization can be a bottleneck.  You should profile or instrument your code so you know exactly which parts take the most time.  If your main loop takes up a lot of time, chances are you need a faster structure to retrieve your min cost nodes.  Currently, I'm inclined to believe that most of your performance is dependent the open list data structure, simply because you stated earlier that the performance depends heavily on the length of the path.


In Topic: Binary heap vs list A* - my humble performance comparison [updated with JPS]

08 January 2014 - 06:13 AM

Thanks for your post, it got me thinking about mine.  I was lazy and just used a built-in structure, the SortedDictionary in C#, but looking at it, it's a red-black tree under the hood so the two main operations I do are inserts, and removal of the top entry and are:

Insert O(log n)   Delete O(log n)

 

While for binary heaps, they are:

Insert O(1)   Delete O(log n)

 

Which, as you can see, will probably give me a decent speed up on maps with large amounts of nodes, though there is no existing BinaryHeap class in C#, so I'd have to write it myself.  (And for now, I'd wager it is not the slowest part of my algorithm by a longshot -- but I'm glad this post made me think about it.)

 

Your running times for binary heaps are wrong?  I'm not aware of any binary heap that functions with those running times.  Fibonnaci heaps may give you that insert time (if my memory serves correctly) but I don't think the delete is O(log n) in the worst case.


In Topic: How to write fast code without optimizing

19 December 2013 - 11:01 PM

Your question seems to imply that you want to write code that is fast/efficient the first time around without having to rewrite it later due to slow performance.  I find that this rarely is the case in practice, although, you can definitely design systems to be more efficient up front or design them to be made easier to optimize later.  But this is incredibly difficult to do.  It requires a lot of experience in algorithms, computer architecture, the problem domain, and just plain programming to be able to know how to write code to make it "fast enough" for your purposes in such a way that you won't have to come back to it later.

 

I've been programming pretty seriously for about 2 or 3 years now in addition to 4 years of schooling from a reasonably good CS program.  I would say I have just enough experience now to sort of see where I can afford to "be lazy" with my programming since I just know it won't make any bit of perceptible difference to the user and where I should definitely think more about the problem before embarking on a coding frenzy since performance might be a concern.

 

It's really difficult (in my opinion) to get a good feel for this other than to just write a lot of code, profiling, inspecting, and really getting to know your code and its relationship to performance.  You eventually get to a point where you can just sort of think about a problem and be like "Yeah, that problem size is so small it won't matter." or "That algorithm might be a little slow, but because I run it only once a frame on a small number of items, it's not a big deal".  If you really know your algorithms and the problem domains, you will be able to easily identify huge red performance flags, like "Oh wow, I definitely don't want to do this A* search in this loop since the graph is thousands of nodes" and therefore spend more time and energy on designing for good performance on those cases instead.


In Topic: What are good ways to implement a "game playback" feature?

17 December 2013 - 09:28 AM

You might want to check out http://www.gamasutra.com/view/news/197635/.


In Topic: Should I make my game engine cross platform?

05 December 2013 - 02:36 AM

  • Have you made a game before?
  • Do you have experience with the operating systems on all the platforms you are thinking about supporting?
  • Are you comfortable with getting into the guts of setting up a proper build system and understand the compilers you'll need to use for each platform?
  • Do you know which language features are supported by the compilers?
  • Are you using libraries which are available on all platforms?

If you've answered no to any of these questions, you almost certainly should not try to make a game that is cross platform.   You'll waste so much time and energy on making something work on all the systems rather than finishing a game on just one of them.


PARTNERS