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.
Posts categorized “Development log”
I’m brainstorming ideas on how to optimize the A* pathfinding algorithm. It looks fast but it will be more complex in the end and I will need it to run even every second for many bots at a time. I need some serious speedup ideas so if you have them please let me know.
Some ideas I’ve been considering:
– splitting the nodes into more general layers (this seems like the easiest approach but thinking about it I don’t see it as correct, how can it preserve information about the cost of the subroutes and shortest path information)
– precalculating the routes into memory (for all routes this will be 100s of MB’s unless there is a smarter way of calculating)
– using network theory (every network has hubs which are critical for the network, maybe utilize this?)
– use the GPU (?)
– calculate the routes iteratively as the game flows, instead of calculating it all at once (this is my best idea yet but it has a minus such that the bot will stand and think for a second before moving to a complicated position. But this is realistic behaviour cause it looks as if a human player is thinking and planning.)
LD Build 1548:
– smoothened run and walk
– fixed getting stuck on cube after jump
– fixed walking in air
– option to disable crashrpt and autoupdate from cmdline
– limited normal mapped lights to 4 (do the ATi HD 4x cards work now?)
– key up can be used for climbing
– actors not loaded if map not created
– fixed climbing through wall in some parts of map
It seems that the crashing on start happens with some exotic video cards and AGP bus cards like:
Intel 945G
VIA/S3G UniChrome Pro IGP/MMX/SSE
Intel Cantiga
Radeon X1050 Series (Omega 3.8.442)
Intel 965/963 Graphics Media Accelerator
GeForce FX 5200/AGP/SSE2
Radeon X1950 Pro
Don’t know why they cause errors besides, that these cards always make problems.
Also all gfx shader and lighting problems give ATi Radeon HD 4xxx cards. Good news is that I can borrow a laptop with this card and try to fix it.
Some crashes might be memory related. Does it fix if you set “v_savememory 1” in Base/Scripts/autoconfig.gm?
I updated the auto-updater to also update the EXE file. You will need to redownload the ld-tech test if you haven’t already http://ping.fm/dAT2K