archive by month
Skip to content

map analysis plans

One of my goals for Steamhammer is to remove the dependency on BWTA, a large, slow and troublesome library. Its startup time to analyze a new map for the first time is ridiculous, and I want full power to analyze map blocks. I could go to BWEM, and I may yet change my mind and do that. But I’m not 100% satisfied; I might have to modify the library to simplify hypothetical reasoning and add features like pathfinding for units which are pushed through minerals. Another idea is to start with UAlbertaBot’s existing distance maps. It calculates ground distances at build tile resolution (32 x 32 pixel tiles) rather than the walk tile resolution of the map (8 x 8 pixel tiles), but this doesn’t cause any obvious problems and is easy to change if necessary. UAlbertaBot doesn’t actually rely on many BWTA features.

I was leaning toward the native distance map solution already. It calls for writing more code, but not that much, and the final solution would end up simpler and better tailored. Now Dave Churchill has made exactly that change to UAlbertaBot. It smooths my path since I can borrow code, and I plan to follow.

Dave Churchill removed BWTA big-bang style from UAlbertaBot, dropping the dependency and replacing its major uses in one step. I think the largest piece was to add a BaseLocation class—not a large piece at all. My implementation strategy will be the opposite. I’ll replace uses of BWTA item by item, testing as I go, and when I’m satisfied I’ll drop BWTA. The development process should be gradual and stable.

As a first step I taught Steamhammer to pay attention to map blocks in calculating ground distance maps. It doesn’t notice when blocks are removed, or route units around blocks, it only calculates distances more accurately based on the map’s initial state. Even this small step improves play, since Steamhammer decides on expansion locations partly based on ground distance. Since I reflexively clean up any code that I touch, I also fixed a bug in checking whether a tile is walkable and reduced the unnecessarily large size of the data structures. Distance maps are better, faster, and cheaper—there should be less memory traffic in calculating a map, and lookups will be more compact in cache.

Trackbacks

No Trackbacks

Comments

MicroDK on :

Will distance maps also include elements like chokes and blocking elements?
And what do you mean by map blocks?

Jay Scott on :

“Map blocks” are what you called “blocking elements”. I’ll have to do something extra for chokes and for map topology (“defending here will keep the enemy out of there”). Maybe I’ll learn better, but I think simple algorithms are good enough.

MicroDK on :

Ahh your post makes much more sense now. ;)

krasi0 on :

As someone who was burned by BWTA peculiarities in the past, I've also gone a similar path - reinventing the wheel with my own terrain analysis library. The most issues I've had have been with a really fast ground distances implementation. In many places, in my code I have to sacrifice accuracy by using air distance instead due to ground distance calculations hurting the performance of my bot.

Are you planning on releasing your improved "distance maps" library once it's finished as a separate open source project? Just curious

Jay Scott on :

It’s a good suggestion. I’ve been reluctant to separate out parts as reusable pieces because they’re a bit too deeply intertwingled [Ted Nelson], but clean APIs are part of good design so it would be a useful step.

Joseph Huang on :

I have a fork of BWEM that compile cleanly on VS2017 and has other minor improvements at https://github.com/bftjoe/BWEM

Jay Scott on :

1. Thanks, that’s interesting. I see the fork fixes at least one severe bug. 2. Your comment is the 1000th published comment on the blog.

Add Comment

E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Form options

Submitted comments will be subject to moderation before being displayed.