Kai Antweiler wrote: >>Thanks for the ideas. I did applied the patch, can you check if they are >>correct, plz. Compile one of them by uncommenting the #define you want: (I >>know >>the name are only the names of the guy who added the new idea, give me a new >>name if you want something politically correct). > > > It looks correct, except for the "else if" part Simon referred to in this > thread.
Sorry, I did miss it, can you tell me exactly how to fix it ? Or fix it directly. > The names shouldn't be an issue since they won't stay long. > Simon works on an improvement which will outperform all others soon. :-) > > > >>In this test, the new algos (Simon+Kai) are actually slower. If I remember >>well, >>it was about 1% faster in 128x128 maps. My conclusion is that the complexity >>added by the simon/kai algo is too high compair to the speed gain. > > > I guess that this performance loss does not come from the increased > complexity of large maps. I was just talking about the algorithm complexity. > The algorithm depends on the order in which > fields that need to be processed are listed. When this sequence > becomes unfavorable, due to obstacles the effect on large maps will be > bigger. (Since the ratio of the distances "resource to obstacle" and > "obstacle to the last field that suffers from the unfavorable order" > will be worse.) That is at least my working hypothesis. > > But Simon has an idea to partition the map like a chess board into > let's say white and black fields. Depending on their "color" the > fields would be processed by different loops (I think?) using two > different lists (each half the size?). > This way a diagonal spreading of gradients can be resumed after an > obstacle causes an unfavorable step. I expect this to become the uber > gradient calculation algorithm. What about processing the various gradient differently depending on its type ? For instance, we have at least 3 types: 1- resources gradients 2- buildings gradients 3- forbidden gradients Theirs statical behaviors are different, and there is probably some speed to be gained out of it. If you think it's useful, I can add structure in the code, so you can access this information. Then I'll let you try to take this into account. Thanks again for the work and ideas! Nuage _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
