Fringe vs A*

Hi all,

So I'm getting close to putting some code to my Navigation and AI designs, but doubt plagues me (I hate back tracking large efforts ). Has anyone had any experience using the Fringe Search algorithm or done any comparison work vs A* (yes I know about the Baldur's Gate II experiment). Any experiments involving Unity would be fantastic! In design principle it would seem to be an excellent option, but I'd like to know in practice how the extra hit to memory models out, and if the gains outweigh the additive costs (I'd like to make a unified code base that works across my iPhone and desktop games).

Anyone?

Galen

 

I doubt its any usefull.

In games A* is the standard and thanks to HPA* and similar "large scale expansions" of the algorithm this won't change till something with comparable performance, scalability, parallelization capabilities and memory requirements will come around (and given how long it has been around that might potentially never be the case - the only thing that changes and gets better and better is the statistical knowledge that leads to better estimation formulas for the remaining path)

 

Well, Fringe is an A* variant, which supposedly saw 25-40% gains over A* in the 2005 experiment, which is why I'm looking closely at it. Interesting, I haven't seen the HPA* before now... It certainly appears to offer some attractive gains. Now I wonder where the trade offs are? It appears memory is sacrificed (as usual), and the preprocessing would naturally provide gain, but ... preprocessing must hit the memory fairly hard?

What I like about Fringe is there is some memory trade offs, but it is essentially the same kind of "real time" node search as A*. Depending on the upfront processing, and memory hits, HPA* looks to be a little impractical for a device as small as an iPhone, unless you did all the level calc and path caching as part of game build, then persisted it, but you still have to restore the data to memory to be useful... That said, it still looks very interesting. At one point I considered Rete for the AI processor, but again, while it can handle (theoretically) any volume of rules without impact from increasing the rule set, it sacrifices memory to achieve it, too much for games in my research.

I would just like to know if anyone has tried Fringe (or even HPA* ) for some real first hand knowledge of any gains vs trade-offs.

Cheers,

Galen

 

The memory hit for HPA* is commonly small compared to the impossibility to calc the path in realtime on a 1000x1000 grid.

What you do in HPA* is basically the same thing as you do with "mipmaps", you have a lower level of detail on the next higher level you search and use "reduced informations there". In case of HPA* you use the gate informations.
Gates are the connections between these higher level grid cells and normally the largest possible connection on such an adjacent grid - grid touching area is chosen for it.


If we take the 100x100 base grid as an example and define the first level of HPA* to use grids of the size 10x10, we would end with a HPA grid of 10x10 cells on level 1 on which we would search the higher level path. Within the cells in the close surrounding we would use the base level grids to search from gate to gate to find the actual path within the world.
if we had 1000x1000, we would take the resulting "level 1 grid" thats 100x100 and find gates there again and make 10x10 cells of "level 1 grid blocks of 10x10" to form a level 2 grid (these numbers are all arbitary just to illustrate the concept for those who never saw it)


this hierarchy (due to the tree nature) requires very little memory and as you can see by the grid still being reasonable small with few cells, does not need too much cpu time.


to my knowledge there are a few different attempts on how to use HPA* and how to work with it so above is just the general idea of it.

 

Also, the original paper seems to make some very dubious assumptions about what goes into an "efficient" implementation of A*. For example, they seem to think using a balanced binary tree to maintain the sorted order of the open list is a good idea, when almost everyone else just uses a priority queue for this. I think the apparent lack of follow-up material to the paper is suspicious, too. A true A* killer would be an achievement worthy of further research, but the few articles I can find about fringe search seem to refer mainly to the original paper.

 

Hmm, interesting. I guess I could implement them all and test them out. Problem is, it ain't as simple as turning out the code from sudo or example. Unity is a runtime based environment, so GC is going to play a heavy factor.

if A* cycles a high volumn of objects, then it won't hold a candle to anything that has a smaller GC cycle curve, unless I can optomize that (which may or may not be "true" A*).

@Andeeee - I never saw the original doc, I found Fringe in my Game Gems (7 I think), but I tend to agree with the principal if you could remove an array sort from every pass, that would be a compelling processing savings. Especially if you're using immutable arrays, with alloc, sort, new arr alloc, dealloc, and GC. But unless I implement and profile, I guess I'll never know.

@dreamora - your description makes sense, but with a Nav Mesh, aren't you really just doing more preprocessing of the map into smaller groupings, then doing parallel processing of the sub-steps? Pathing would still need to maintain the shared perimeters as the step triggers, unless you use coord ranges... hmm (I type out loud when I think sometimes)...i see... However... if it's more efficent, then substuting Fringe for A* at the search layers should theoritically improve the HPA*, if Fringe does prove to be faster, would it not?

Thoughts?

Galen

 

I don't see how the nav mesh is impacting HPA* at all. Instead of a grid you would just do the sectorization basing on a mesh and define the gates as passable passages between the sectors.

A* / HPA* don't really care about the kind of data you use as long as it can be pathed.
You get a little overhead for generating the layers, but if your game really requires longer range searches (RTS) then it will be unavoidable to pregenerate some basic knowledge over long range pathing anyway.

For FPS and alike HPA* is only required on a restricted level, as you never want to do long range searches there anyway, its all happening in a pretty small perimeter normally.

 

AI Game Dev. Has a paper on a new algorithm SHPA*

http://aigamedev.com/premium/articles/static-hierarchical-pathfinding/

 

thats just one of quite a few papers, articles and videos on A* / HPA* on AI GameDev though some are premium only like this one

 

Ya I never like when they do that. Half their stuff is like that.

 

the quality of the stuff and the kind of professionals they get to contribute more than justifies that. I've had an indie commercial since the service launched and I've owned Alex book for quite long too and was wading around the page when it was primarilly the page of the book and the home of the "framework" that existed)

Already the sandbox and its sources kind of justifies it.

people that want half baken and outdated stuff can find a good home at aidepot

 

Which, ironically:

But of course Alex's efforts are into AIGameDev, and a subscription is well worth it.

 

You can find it here and it's quite short, so well worth checking out.

Well, my point was that in practice, you don't sort the array on each cycle but instead use a priority queue. This essentially means that you are adding new items to an already sorted or partially sorted list, which is much faster than sorting from scratch each time. (It can often be more or less constant time, which is the supposed benefit of fringe search.) Also, the GC performance is only roughly the same as for maintaining the fringe search's now and later lists. I still think fringe search could potentially be faster, but I don't think the difference in reality is anywhere near as great as the paper claims.

 

hehe, well, as you know, there are lies, damed lies, and performance statistics

There are simply too many factors to make sweeping generalizations about actual impact of given algorithm, without at least factoring programming language, platform, and certain key aspects of implementation (green threads, native threads, physical constraints, OS, background tasks/procs, etc...).

I find your comment about maintaining the lists being a impact puzzling. Other than available memory what do you see as the impact there? I have spent many years working with the Java Virtual Machine, and while I know little about the .Net implementation, I can't imagine that the pain points aren't very similar.

One of the biggest (if not the biggest) hits to performance is GC cycles. I assume (and please correct me if I'm wrong) that it's a standard mark and sweep (2 cycle) GC, unless they're doing address blocks (ye gods!). Is the GC in .Net (or Mono in this case) a "stop the world" GC cycle or concurrent? Java takes hits on Heap expansion, Heap contraction, and can bottom fast with what I call "GC trashing", large extended object allocation followed by long GC cycles that creates a "Rockies" looking performance graph. Is that the same in this case?

In my experience with Java, maintaining a relatively flat memory usage with low object turn over (relative to scale of course) with short GC cycles is your ideal performance model. So a near fixed size array would out perform short lived object creation every day.

That reminds me, can we tune the Mono heap and GC settings?

Inquiring mind (I won't go so far as to drag others into my sick world .. they may walk in on their own but consider this your fair warning :twisted: ) wants to know

Cheers,

Galen

 

You can read about Monos GC and its future 2.8 here.

http://www.mono-project.com/Compacting_GC

 

the gc used in Unity at the time is not even remotely comparable to that.

Unity is Mono 1.2.5 and the GC has changed twice pretty indepth since then (or even 3 times?)

 

ya but unity 3.0 will be mono 2.6, may as well develop with that in mind. Or, even be forward looking to the new GC.

 

yupp with unity 3 it will switch

But thats still months away

 

Although, iPhone 1.6 already uses mono 2.6.

 

Ye gods man! Are you saying that a compacting GC is the "future" 2.8 release? Please tell me Microsoft is doing something more with the .Net GC? :?

I hadn't even considered the possibility that Mono wasn't doing a compaction cycle.... So.. hmmm... I guess I shouldn't plan on a really long running session. How in the name of all that's unholy does the Unity game server stay up for any period of time? Or are you sneaky Unity folks doing something more under the covers (explaining the long pause between Mono integrations)?

Now you got my attention...

Cheers,

Galen

 

.net's GC is significantly more advanced. It is a precise compacting GC. Although some here will disagree with me .net is generally significantly more optimized then mono.

The only area I can think were mono maybe more Optimizable then .net is intrinsic functions. However, they are still incompetent and I think that underlying implementation details of mono are holding up their completion at least to a degree.

http://tirania.org/blog/archive/2008/Nov-03.html
http://go-mono.com/docs/index.aspx?tlink=0@N:Mono.Simd

They are doing something different under the hood its called c++.

 

That's not really an indication of how they've implemented change in the Unity Mono implementation. The current mono GC is a C/C++ simple GC api. I'd be surprised if mono isn't c/c++. my question was really, have they implemented a better GC in their port of Mono.

I'd have been more impressed if you'd said they did assembler, or PL/x something. C and C++ are still only 3rd gen languages like Java, compilers factor heavily in this space.

Cheers,

Galen

 

I meant their net code is a managed Raknet wrapper. I have not heard anything about them making a different GC for mono. I doubt they would as they view mono as a scripting language platform. The internals of the engine are all c++ or whatever.

I think the long lead-time had other reasons
http://aras-p.info/blog/2009/11/14/improving-cmono-for-games/

 

Well, the lists in fringe search are arrays that are extended whenever they get full. You can implement A* using small structs to represent the open and closed list elements, so again you effectively end up with two arrays that get reallocated only when full (ie, if you use structs, you don't allocate each element individually). I'm really just saying that, although A* is often implemented with a lot of dynamic objects (== allocations/GC) it needn't be done that way. The GC overhead of maintaining the lists should be roughly the same for either algorithm.

 

Hi,
Sorry for poping up this old thread.

I am a new member. Forgive my english.

I actually work on a benchmark involving different pathfind algos on large maps. (one is a "classical" A* with heapsort, the second has a sorted linked list with dichotimic insert, the third one has the open list quicksorted, the forth one is fringe search)

The goal is only theorical. Of course, i realize using the second algo with a fixed list length of dozens of nodes would be faster and easier... But pointless.

Actually my algos are finished except the fringe search one.

In fact it seams the pseudo-code may be wrong, so i had to adapt it. (at the moment i am writing, my fringe code works well for obstacle-free path... I don't know what i am missing. Whatever it's already the fastest one of all algos i tried)

For exemple the initial threashold equal infinite is a problem.

As only few persons feel concern by fringe algo on the net, i am hoping one of you may help me to correct the pseudo-code.

Like you said, every article refering to fringe search give more or less the same "wrong" pseudo code and probably nobody test it.

I sent a mail to Mr Bjornsson, but no reply for the moment.

 

Well this is interesting as I now understand this stuff from taking an AI class this past fall at my University!

I read over the entry on Fringe on Wikipedia and it sounds like its only advantage is memory. I did note that the wiki entry also mentioned things about an inefficient implementation of A* assuming a truly random and even completely jumbled open list to sort each iteration. So, I would say A* is fine unless you are doing some crazy RTS AI, but really, RTS AI is done in masses. Select all the units and click a point, one path is generated and all move to the path and follow the one path. So really, unless you are targeting low end systems and mobile devices I wouldn't worry about the memory constraints on A* unless you have a large volume of enemies on screen, but I would assume you would run out of draw calls before memory on modern systems.

A good implementation of A* keeps a sorted list to explore and when nodes are added its a very quick sort as the list is already presorted. At no time should the open list be completely randomized as each item is added and sorted. Very quick operations and no long calculations. The best implementations of A* do processing in constant time with linear space(if I am not getting it confused with some of the other algorithms we studied). Fringe sounds good if memory is an issue, otherwise A* is a quick a dirty(can use a lot of memory depending on total nodes in the path) way to get from point A to point B.

 

I think fringe search is a very interesting algo. I don't think it improves memory except if you use a cache with a hashing. But it definitely improves speed.
As i said, i can't yet say, as far as the comparison is not done but clues indicate it's more than 20% faster than a good implementation of A*. (and i say good because we can not use "the best" but it's the idea)

Game industry already uses A* with a reduction of the amount of nodes and abstraction like HPA, PRA TRA etc...
But fringe search improves speed in any of them. (cf Pathfinding with hard constraints) Obviously it's not a necessity as far as it's already fast enough.
So, we can always use old good recipes that work, or we can evolve and think outside the box.
Of course, today it's asked to do fast job and creativity is not the priority. But sometimes it's useful to shake the basics to see what happens.

This is the pseudo code :

Code (csharp):

1.  
2. init
3.   fringe F = s
4.   cache C[beginning] = (0, null)
5.   for n in C, n != beginning
6.     C[n] = null
7.   threshold = h(start)
8.   reachedgoal = false
9.  
10.   while NOT goal=true AND F NOT empty
11.     fmin = ∞
12.     for n in F, from left to right
13.      (g, parent) = C[n]
14.      f = g + h(n)
15.      if f > threshold
16.        fmin = min(f, fmin)
17.        continue
18.      if n = goal
19.        reachedgoal = true
20.        break
21.     for s in children(n), from right to left
22.       g(s) = g + cost(n, s)
23.       if C[s] != null
24.         (g', parent) = C[s]
25.      if g(s) >= g'
26.         continue
27.       if s in F
28.         remove s from F
29.       insert s in F past n
30.       C[s] = (g(s), n)
31.       remove n from F
32.     threshold = fmin
33.  
34.  if reachedgoal = true
35.    make path from cache

You can see, at the beginning the node inside the now list is the start node alone.
the threshold=h(start)
then first iteration:
f_min= infinite
g=0
h=h(start)
f=h+g=h(start)

we skip the test as f=threshold (and not superior)

then at the end,
threshold=f_min= infinite

next iteration and forever it will stay equal to infinite.

Maybe it's obvious but it seems to me there is a problem there...