I was just shocked at how someone can optimize code. I used Justin Heyes-Jones (http://ping.fm/ui2zB) implementation of A* for pathfinding. It took 31s to calculate a route from one end of the map to another. Now I found this by someone called Konstantin Stupnik (http://ping.fm/TiUPL). He optimized Justins code by using heaps and hashing. I thought it would optimize the algorithm 2-3 times. For the same test from one end of the map to the other the calculation took 0.03ns ! I guess I don’t need anymore optimizations.
Written by MM. Posted at 10:14 am on January 10th, 2010
23 comments.
Post a comment.
” any more optimizations” ;p
anyways good news! looking forward to a vid with many bots on many paths. also, what is the source of collision problems?
Wow!
Either that Kontstantin is a genius or the original code was more of a “basic template”
I don’t want to be a smartass, but 0.03 nanoseconds seems to be impossible. That’s less than one clock cycle on a regular CPU. I’m just curious on how much it really sped up.
Did you mean 0.03ms?
Konstantine writes that his improved algorithm is up to 10 times faster than the original one. Even if MM means milliseconds the algorithm would be more than a 1000000 (one million) times faster..?
Did you mean 0.03 seconds?
Using a binary heap for the open list was one of the suggestions I was trying to get through yesterday.
Bullshit 0.03ns, only the IBM roadrunner cycles THAT fast. And i have a strong feeling, you are not in possesion of anything nearly as fast. So how the fuck did you come up with 0.03 nano seconds?
Probably a typo or MM lied to us 😮 (Oh noes!)
Yeah sorry its 0.03ms. That would make it 100 times faster. But he used for testing a basic 2d tilemap. My map looks more sophisticated but in fact isn’t and is even faster.
hmm 31 s / 100 = 0.31 s ; 1 ms = 0,001 s ;
0.001 s * 0.03 = 0.00003 s; so it would make it 100 000 times faster?? or i just got a very bad sleep 2day.
can you give us a brief preview of what the commands are going to be ? how to control your team ? and even maybe some of the equipment and selection options ? give us a new release time for this new addition to the engine
Am I so bad at math?
0.00003 * 1000000 = 30.0
0.00003 * 1033333 = 31.0
More than 1000000 times as fast as the original algorithm, no?
Poersch, you’re right (unless MM misspoke again^^).
wtf, who cares? its faster and its fast enough..so goodjob mm!
It’s a 1000 times faster. Cool.
so what was the actual time mr bullshit? 0,031 s? it’s 31 ms. no wonder u have so much bugs when u make math mistakes like that ;p
LEAVE MM ALONE!
It’s about 10,000 times faster. 1 Second is 1,000 Millisecond. 31s/10000=0.03ms.
Very fucking simple.
The important news is it works even in realtime calculating every frame without a significant fps drop.
@Makron666
31s / 10000 = 0.0031s = 3.1ms
You’re missing a factor of 100, which finally gives us a speed-up of 10^6 (one million)
@MM
Well done, I’m looking forward to seeing your bots in action
We can be certain of only one thing, that the optimization increases the speed by a factor of over nine thousaaaand!!!
i guess both units are meant to be milliseconds >.< So it's about 1000 times faster as mm already said. I mean.. "31s to calculate a route"? Come on, half a minute sounds like the game is turn-based (email-based multiplayer or something).
seriously ppl? SERIOUSLY? math wins.
los costos de estas cosas son siempre muy muy altos, una pena vemntderaredae.En mi opinion, pagar cursos es como botar la plata, sale un poco mas caro pero prefiero un profe particular solo para uno, para practicar el hablar y perderle el miedo, y en los veranos, hacer el “travel and work” a EEUU o a Australia/Nueva Zelandia.