I feel really silly for having trouble working this out, but I’m building a strategy game that occurs on a uniform grid, and I’d like to retain and regularly update a heatmap that tracks how attractive every grid square is a variety of ways: proximity to water, other settlements, resources, and the like. The problem I’m having is that even on small grids (the current game world is 512x512) it isn’t feasible to compute an “accurate” heatmap, since manually computing proximity scores that are weighted by distance means comparing each square to every other square, which is well over 260,000 operations.
I could check the immediate environs around a grid square, say 4-5 coordinates out in every direction, but that will lead to some weird clustering where the AI will be unable to tell the difference between a giant swatch of resources that it should prioritize at all costs, and a much smaller patch that happens to be just big enough to max out the proximity check’s radius.
So is there a happy medium for this? It sounds like a silly thing to be scratching my head over, but as the map gets increasingly dense I find it becomes more and more important to weight the entire map’s structure in order to generate quasi-believable behavior.
lf you batch let’s say 64 squares into one “chunk” and calculate for each of these, and then calculate all the chunks, maybe give it a couple special cases like “hey the next chunk next to this has a mega-huge resource pile” or “the chunk next to this is part of an enemy base(if you have war in your game)” to give the AI a bit more of awareness.
using 64x64 chunks gives you 4096(per chunk) * 8(chunks in a 512x512 grid) = 32768 operations for each tile, it scale way less worse with big map sizes and you’re left with just an 8*8 grid to calculate to trim the gaps.
assuming i done my math right cause im high, hope this helps.
Consider using a quadtree. If the entire upper left quadrant has no water, for example, your AI can eliminate the whole quadrant from consideration. If it has a significant amount of water, you can drill down into it and check which of its subquadrants has the most water, etc.
