Smart AI vs Expensive AI

[mushroom patch]

Okay, if that's what you mean, I admit that's potentially a more expensive case. It's still true, though, that generating exploration pathing is not super expensive and does not need to involve much calculation per turn on average. I don't know if you've read the "Dijkstra map" article the author of Brogue wrote, but it mentions this use case. My impression is that this can be done fairly cheaply by iteratively updating an existing Dijkstra map as more dungeon comes into view. There would be some memory overhead for sure, but you can work out schemes to keep this under control if you're really worried about it (my feeling is that it's probably no big deal).

Using the Dijkstra map approach gives you certain advantages in that if you're serious about computing real FOVs now and then for "realism," you can do these calculations only when the Dijkstra map tells you you're adjacent to previously unFOV'd tiles. You can do likewise if you use a cheap FOV approximation, like the one I describe above.

[Kevin Granade]

I'm curious, outside the "hunger games" like scenario, where are you envisioning using fair exploration?

[reaver]

Okay, if that's what you mean, I admit that's potentially a more expensive case. It's still true, though, that generating exploration pathing is not super expensive and does not need to involve much calculation per turn on average. I don't know if you've read the "Dijkstra map" article the author of Brogue wrote, but it mentions this use case. My impression is that this can be done fairly cheaply by iteratively updating an existing Dijkstra map as more dungeon comes into view. There would be some memory overhead for sure, but you can work out schemes to keep this under control if you're really worried about it (my feeling is that it's probably no big deal).

Using the Dijkstra map approach gives you certain advantages in that if you're serious about computing real FOVs now and then for "realism," you can do these calculations only when the Dijkstra map tells you you're adjacent to previously unFOV'd tiles. You can do likewise if you use a cheap FOV approximation, like the one I describe above.

I've already implemented distance transforms, it's fast for path evaluations and memory heavy, and would work reasonably efficient for a given radius around the agent instead of the whole level -- naive updates are too expensive in my opinion, but I haven't tried to optimize it very thoroughly tbh.

I'm curious, outside the "hunger games" like scenario, where are you envisioning using fair exploration?

AI agents appearing to be playing like the player, exploring the same dungeon for example. "The king sent a bounty for the head of the orc marauder leader who's hiding in the cave of woes. Who will be the first to bring it back?"
Yes for the above I can craft some fake AI that appears to be doing that, but I don't want to craft one per such scenario.

[mushroom patch]

Okay, if that's what you mean, I admit that's potentially a more expensive case. It's still true, though, that generating exploration pathing is not super expensive and does not need to involve much calculation per turn on average. I don't know if you've read the "Dijkstra map" article the author of Brogue wrote, but it mentions this use case. My impression is that this can be done fairly cheaply by iteratively updating an existing Dijkstra map as more dungeon comes into view. There would be some memory overhead for sure, but you can work out schemes to keep this under control if you're really worried about it (my feeling is that it's probably no big deal).

Using the Dijkstra map approach gives you certain advantages in that if you're serious about computing real FOVs now and then for "realism," you can do these calculations only when the Dijkstra map tells you you're adjacent to previously unFOV'd tiles. You can do likewise if you use a cheap FOV approximation, like the one I describe above.

I've already implemented distance transforms, it's fast for path evaluations and memory heavy, and would work reasonably efficient for a given radius around the agent instead of the whole level -- naive updates are too expensive in my opinion, but I haven't tried to optimize it very thoroughly tbh.

Yeah, a kind of lazy evaluation scheme based on distance from updated squares and squares being read for pathing should make it pretty efficient.

[Bear]

Line of sight calculations don't have to be expensive.  In fact, you can nail them down to a range check and a common-bits check on a 64-bit bitmap.  I blogged about this technique recently.

http://dillingers.com/blog/2014/05/29/roguelike-ai-8/

It's basically a way to do the field-of-view calculation at dungeon generation, and cache the result as one 64-bit bitmask per square.  It makes map generation take a second or so longer depending on your CPU (well, and on the map itself; some are harder than others).

As I initially developed it, it was a fast, approximate field of view suitable for monsters - It could be wrong sometimes.  But the current algorithm makes false positives impossible and allows you to mark the few imperfect squares where you might get a false negative. 

So in the one-out-of-ten-thousand or so cases where both the viewer and the thing it's trying to view are in imperfect squares, you can do the quick check (because if it says LOS exists it's always right because of "no false positives") and if it fails you might have a "false negative" in that case so you can do a conventional line-of-sight check if you need perfection.

You do have to recalculate your bitmasks when someone digs opening new line-of-sight.  But that's rare enough that it doesn't cause much problem.



Pathfinding isn't particularly expensive either;  Most pathfinding is chase and follow behavior centered on the player character, and sight gradient pathfinding is very good for that case and works in constant time.  Another recent blog article:

http://dillingers.com/blog/2014/05/16/roguelike-ai-6/

Because you have to traverse the map anyway, each turn as the player character calculates FOV and track which squares are in view, you can get sight gradient pathfinding essentially for free: Track which squares are in view by writing a number into them (a number calculated from current turn and distance from player).  Thereafter, any monster standing on a square the player has ever seen can pathfind to the player simply by stepping into the neighboring square with the highest available sight gradient number.  It works so well for chase-and-follow that you have to limit it to avoid being grossly unfair.

Doing more general pathfinding with A* or Dijkstra's algorithm is relatively expensive, but it doesn't have to be expensive per monster:  You can share the cost of pathfinding across all monsters that have the same goal point (or set of goal points) and movement costs by having them use a common pathfinding-cost map, and calculate based on navigation costs from the (shared) goal points to the (individual) origin points instead of the more usual origin-to-goal direction. Another blog post, covering this technique in the context of escape and avoidance.... 

http://dillingers.com/blog/2014/06/15/roguelike-ai-9/

That way when ant 234, which is pathfinding to one of the same set of goal points as ant 221, considers a square whose navigation costs were already calculated back when ant 221 was pathfinding, those navigation costs already cached are valid for ant 234 as well.  In the reductio ad absurdum case, ant 234 may even be standing on a square whose navigation costs were already calculated for ant 221, so ant 234 gets its navigation entirely for free. 

Finally, there are good cheap ways to reduce navigation costs even more.  First of all you can use a navigation table (hmm, I guess that's a Roguelike AI article I still need to write) to handle longer-range navigation.  Each entry in a navigation table is a map segment within which navigation is essentially trivial - a room, or a straight-ish chunk of cave or corridor.  Special squares called 'waypoints' are in both of two (or maybe even more than 2) segments.  And part of map generation is to 'parse' the map into segments and build a navigation table. 

Then you can define a 'magic navigator'' function where you tell it "I'm at square X Y and I want to get to square P Q, which way should I go?"  and it just tells you in constant time.  The way it works in the background is, "Square X Y is (lookup) in segment 9, Square P Q is (lookup) in segment 22, the best way to get from segment 9 to section 22 means first moving to (lookup) segment 11, and to get to segment 11 from segment 9, you go (lookup) to square M N which is the waypoint between 9 and 11.  And square M N is (simple math) NorthEast of square X Y. "

Will the navigation table always find the best solution?  If you get fiddly and deal with a lot of corner cases and movement-cost lookups and end-segment navigation cost calculations you can make it find the best solution.  But that's hard. It's flatly easy to make it find a damn good one and find it fast.

[reaver]

Line of sight calculations don't have to be expensive.  In fact, you can nail them down to a range check and a common-bits check on a 64-bit bitmap.  I blogged about this technique recently.

http://dillingers.com/blog/2014/05/29/roguelike-ai-8/

It's basically a way to do the field-of-view calculation at dungeon generation, and cache the result as one 64-bit bitmask per square.  It makes map generation take a second or so longer depending on your CPU (well, and on the map itself; some are harder than others).

As I initially developed it, it was a fast, approximate field of view suitable for monsters - It could be wrong sometimes.  But the current algorithm makes false positives impossible and allows you to mark the few imperfect squares where you might get a false negative. 

So in the one-out-of-ten-thousand or so cases where both the viewer and the thing it's trying to view are in imperfect squares, you can do the quick check (because if it says LOS exists it's always right because of "no false positives") and if it fails you might have a "false negative" in that case so you can do a conventional line-of-sight check if you need perfection.

You do have to recalculate your bitmasks when someone digs opening new line-of-sight.  But that's rare enough that it doesn't cause much problem.

Blog article rant:
Read your blog post but it needs a LOT of reading and re-reading to make sense. Your code bits have different conventions, you never explain some other stuff (what's the "seed tile?" why do the cells need sightmasks and blindmasks? their purpose is also confusing). Sorry if I sound ungrateful and I understand that this is stuff done in one's free time, but I think a lot of good info can be found in those posts (definitely what we need more of here) but they're kinda lost in the writing (to me at least, others might feel this is primary school reading stuff).

FastLOS:
Did I understand correctly that some bits of the mask, e.g. bits (2,4,5) at a tile (x,y) might refer to view areas that is far, far away from the tile (thus the mask value is definitely 0)? If that's the case, why don't you apply some sort of spatial subdivision, so that while for example you might have 512 different view areas, you can spatially organize them in 4 quadrants of the map and then each tile would only need to reference 128 of them based on the quadrant it belongs to.

[mushroom patch]

Maybe this is a stupid question, but it seems to me that if you're willing to precompute FOV for every square (which doesn't seem crazy to me), why not just throw all mutually viewable pairs into some constant time access collection? In a reasonable dungeon layout (like, one with tunnels and walls and stuff), this shouldn't turn out to be all that much stuff. If you don't care about improbable false positives (which I think is a reasonable compromise), you can use a Bloom filter to keep the memory use under control.

[reaver]

Maybe this is a stupid question, but it seems to me that if you're willing to precompute FOV for every square (which doesn't seem crazy to me), why not just throw all mutually viewable pairs into some constant time access collection? In a reasonable dungeon layout (like, one with tunnels and walls and stuff), this shouldn't turn out to be all that much stuff. If you don't care about improbable false positives (which I think is a reasonable compromise), you can use a Bloom filter to keep the memory use under control.

Just tested that on a standard dungeon layout with regular-sized rooms (floor tiles width/height in the range [3,12]).
A 80x25 map resulted in:
(los, num pairs)
5 - 25986
6 - 30468
7 - 34249
8 - 37429
9 - 39637
10 - 41155
11 - 42081
12 - 42663
13 - 43180
14 - 43537

A 160x50 map resulted in:
5 - 107670
6 - 131249
7 - 151895
8 - 171392
9 - 186844
10 - 198563
11 - 205985
12 - 210806
13 - 214729
14 - 217279

A 320x100 map resulted in:
5 - 440266
6 - 539836
7 - 628595
8 - 713143
9 - 781102
10 - 833547
11 - 868075
12 - 891653
13 - 909962
14 - 921859

So let's take the hardest case so far : 320x100 with max LoS range = 14. We can use a map: (point, point) -> bool. For reference, if we use an std::set where entries are visible pairs, I got 70MB in a debug build and 30MB in a release build (latest MSVC compiler).

But, we can also store the pairs (points A and B) densely, in which case we need:
Sort A and B along one axis.
16 bits for the linear index of the point A in the map (as 320*100 < 32768)
4 + (4+1)  = 9 bits for storing the unsigned/signed offsets of point B from point A ( up to a max offset of [0,15] [-16, 15] for the unsigned and signed offsets respectively)

So, 16+9=25 bits (4MB) is not *that* bad  for a blazing fast FoV check for the given map and max LoS range, is it?

The 320x100 map, for reference: 

And as the storage is dense, it is independent of your map (dungeon, overworld, cavern, whatever)

[tuturto]

So, 16+10=26 bits (8MB) is not *that* bad  for a blazing fast FoV check for the given map and max LoS range, is it?

"When you bow in one direction, you moon to the other direction" (old jungle saying).

But with the amount of memory modern computers have, that's not bad at all. That's actually starting to sound really tempting.

[reaver]

Eliminated a single redundant bit above, 1 bit less required, half the storage cost needed.

[mushroom patch]

Cool, thanks for trying it. I'm a bit embarrassed to say how much time I've spent thinking about complicated LoS caching/precomputation schemes, in view of how simple this scheme is. This doesn't sound too bad, memorywise. I mean, it's not like 8 mb of memory is hard to come by.

[reaver]

You're not the only one thinking too much about complicated LoS / FoV, tons of people are probably 'guilty' of that around here, myself included, thanks for the thought that triggered the testing! Gonna actually properly implement that and see what happens.

[mushroom patch]

Nice, I'll be interested to hear what happens. I guess this kind of scheme is easy (or at least not too hard) to update on changes to the level too -- e.g. if you dig into a wall, you really only need to look at the FOV of the newly empty square -- if you're using a straightforward set data structure (vs. something fancier like a Bloom filter).

It would be nice to see how the performance of something like this compares to more conventional line of sight calculations on average, if you find time to run a simulation.

[Bear]

Blog article rant:
Read your blog post but it needs a LOT of reading and re-reading to make sense. Your code bits have different conventions, you never explain some other stuff (what's the "seed tile?" why do the cells need sightmasks and blindmasks? their purpose is also confusing). Sorry if I sound ungrateful and I understand that this is stuff done in one's free time, but I think a lot of good info can be found in those posts (definitely what we need more of here) but they're kinda lost in the writing (to me at least, others might feel this is primary school reading stuff).

Sorry.  It's often hard for me to know what will and won't be understandable to others; and if I blow it, I often need help figuring out where it went wrong.  The "seed tile" is just the floor tile that you start the iteration with.  The iterative process allows you to add tiles to a set, but doesn't work unless you already have at least one tile in the set.  So you can't start iterating until you pick one to serve as the 'seed' and add that to the set.

I will accept any help I can get in polishing blog articles, so feel free to comment on them.  I've been thinking already that I need to go back and add a bunch of graphics.  Most people seem to understand things better with graphics.  I'm having trouble figuring out what they should show though.

FastLOS:
Did I understand correctly that some bits of the mask, e.g. bits (2,4,5) at a tile (x,y) might refer to view areas that is far, far away from the tile (thus the mask value is definitely 0)? If that's the case, why don't you apply some sort of spatial subdivision, so that while for example you might have 512 different view areas, you can spatially organize them in 4 quadrants of the map and then each tile would only need to reference 128 of them based on the quadrant it belongs to.

There is no circumstance in which a bit in a sight mask at tile (x,y) refers to any view area all of which is out of range from tile (x,y).

At a given tile (x,y) any bits of the mask that are 1 refer to local view areas that the tile is part of.  Bits that are 0 may be unset just because they weren't needed. Otherwise they are unset because 1's at those locations would be interpreted to mean that the tile is part of some view area within sight range - and 0 means the tile is not really part of that view area.   

One bit of the sight mask may be used in one part of the map to refer to one view area, and reused elsewhere (where the range check from any part of that view area will fail) referring to completely different view areas.   But another bit of the sight mask may be used for the view area represented by a single straight corridor that that goes all the way across the dungeon, where most of it will fail the range check from any single location inside it. 

In cases like the first, the spatial subdivision between view areas not mutually visible happens as a result of the sight range (distance) check.  In cases like the second, it's more efficient use of mask space to just use a single bit for a single view area, even if the view area cuts across a much larger space than you can actually see at one time or cuts across what would otherwise be a bunch of different spatial subdivisions. 

The blind mask is not needed during gameplay; it's only used during generation of the sight masks.  Its purpose is to keep track of which bits in the sight mask cannot be assigned at a given location. In fact, its purpose is to achieve the same spatial subdivision you were asking about. 

When we decide that we will use (say) bit 5 to represent a view area, we mark bit 5 in the sight mask for all the tiles in that view area.  But then we have to also mark bit 5 in the blind mask of all the tiles within sight range of any tile in that view area to remind us not to use bit 5 for any view areas those other tiles are in.  Otherwise, we might use bit 5 for some different view area some of whose tiles are in sight range of tiles in the first view area.  If that happens, then the range check succeeds and the sightmask AND succeeds - and suddenly for no in-game reason actors get the ability to see into this other view area, regardless of what's between them.  That would be bad.

[Bear]

Maybe this is a stupid question, but it seems to me that if you're willing to precompute FOV for every square (which doesn't seem crazy to me), why not just throw all mutually viewable pairs into some constant time access collection? In a reasonable dungeon layout (like, one with tunnels and walls and stuff), this shouldn't turn out to be all that much stuff. If you don't care about improbable false positives (which I think is a reasonable compromise), you can use a Bloom filter to keep the memory use under control.

No, it isn't stupid.  It's much simpler and easier to get right than what I wrote. I didn't really consider it because the storage requirements are O(n^2) rather than O(n).  I don't think it really matters though at the scale I'm considering in practice. 

Let me think...  My 'mapchunks' (one level per mapchunk, in most cases) are 100 x 100, so 10000 tiles per level.  So the storage requirement per mapchunk, using one bit per tile pair, is (10000x10001)/2 bits = 5005000 bits, or about 5 megabytes.  That's too chunky for a phone, but not outrageous on a desktop machine. The way I'm doing it, with a 64 bit mask per tile, is 640000 bits or a bit over a half-megabyte. 

So you'd get much simpler code, easier to debug, and about the same speed modulo cache issues, and I'd get a savings of about 85% in memory devoted to speeding up line of sight checks.