Temple of The Roguelike Forums
Development => Programming => Topic started by: MisterMoxxie on June 22, 2014, 10:06:19 PM
-
Hey, there, Temple goers!
One of my driving motivations in developing a rogue-like has always been doing an interesting AI system, one that could produce results that would surprise the players, as well as myself. I've got some pretty interesting ideas on how I want to set the system up, how I want my creatures to react to certain things, etc. However, I can't get around one major stumbling block.
In the design process for a smarter AI system, one obvious thing comes up. Creatures need to be able to 'see' what is around them, in order to react to what is there and choose what task they're going to focus on. I've been trying to wrap my brain around a way to do this, without just calling a ton of field of view algorithms every time a monster moves or takes a turn.
The only plausible idea I have come up with, so far, would be to allow creatures to see everything that is in the room they are in. Then, when populating the dungeon, each room would contain a list of all objects that are in that room. It seems like it would work pretty well. However, when the creatures are in hallways or otherwise in between rooms, I would still have to do some sort of FoV call.
What are your guys' ideas? By the way, I'm using Libtcod 1.5.1 and Python, but it's a pretty general question, really.
Thanks in advance!
-
When the AI is close to the player, use FoV for fairness. When not close, you have several options. Use FoV indiscriminately. Cheat. Approximate. The last is the wisest choice IMO.
-
Two possibilities:
Let monsters see everything within a certain distance. This sort of unrealism will not make your monster AI less interesting.
Use a cheaper proxy for vision like what you're talking about. For example, along the lines of what you're talking about, you can make a partition of your level by taking each room to be a piece of your partition. Fill out the rest of the partition according to the following procedure:
1.) pick a tile not already in your partition
2.) take its field of view
3.) remove all tiles in the field of view already in other pieces of the partition
4.) take the connected component of the resulting set that contains the starting tile
5.) repeat with other tiles until every tile is in the partition
Now you can record which pieces of your partition are adjacent to each other in a graph-like data structure. There are lots of libraries that provide such data structures, often with lots of interesting things you can do with graphs, but you could roll your own basic graph data structure easily enough. Mark each tile with an identifier so you know what piece of the partition it's in and keep a list of objects (updating as necessary) that live in each piece.
Once you have all this (not that hard to code since you already have the field of view part from libtcod), you have an easy to compute proxy for line of sight: Say a monster can see an object if the partition piece the monster's in is adjacent to the one the object is in. This is a very cheap (almost everything is precomputed), reasonably good approximation to line of sight, particularly if you make reasonably intelligent choices of initial tiles in the partitioning scheme above. If you have very irregular dungeons (e.g. tightly winding mazes or caverns), you may need to do a little more to make this produce reasonable AI, for example you may want the approximate line of sight to take more than one jump in the graph described above.
-
Are you looking to have anything other than reflex agents?
-
Hmm. Thanks for the ideas, guys! I like the idea of using partitions, I'll definitely look into that.
@Requerent, what do you mean by reflex agents?
I want my creatures to have tasks/goals, not just be randomly wandering around until they see something, and then try to kill/run from it. Creatures will have values that give them some sort of 'personality' (ie aggression, greed, focus). A creature with more greed than aggression, would rather spend its time looking for treasure in the dungeon and hoarding it (either on themselves, or in a room/container). However, if that creature sees the something wearing some fancy armor / jewlery or weilding an expensive-looking weapon, it may decide to attack anyway. Where a creature with a high aggression will basically attack anything that gets too close to it. The 'focus' value would help to determine how easily they are distracted from whatever task they are currently focusing on.
This is just one set of examples, I have a lot of interesting ideas floating around that I may or may not end up implementing. But, basically, my goal is to have an AI that can run my non-enemy as well as my enemy creatures, and one that could produce results that may even surprise myself.
Trailing off a bit, I've also had an idea of doing a side-project with libtcod, using AI and neural networking in a sandbox-esque environment. This would also allow me to test how certain creatures react to each other, or other unorthodox AI implementations I might have, such as AI that actually 'evolves' and 'learns' to an extent.
-
How will the player know why a creature is attacking the player/another creature?
How will the player know that a creature has a goal or destination in mind when they first see it compared to it standing perfectly still?
How can the player tell the difference between a creature that has specially hoarded the gold in its room/on its person compared to the same creature that spawned with those things already in place?
How will a standard enemy AI with one special ability learn/change in such a way that the player can tell the difference in the 5-10 turns it takes for that creature to be killed?
Sorry to be a downer, but the thing about interesting AI, sadly, is that it most often only ends up interesting from the back end.
-
also it depends on your game mechanics:
realtime or turn based
If it is turn based, you probably won't see or understand complex ai
If it is realtime, then there are a lot things to deal with first, the main one being "trapped in corners" - get a simple movement that doesn't get trapped first then build a second behaviour. after you add a behaviour - check it works and your monster doesn't get trapped, or stan in one place going round in circles, etc
-
How will the player know why a creature is attacking the player/another creature?
How will the player know that a creature has a goal or destination in mind when they first see it compared to it standing perfectly still?
How can the player tell the difference between a creature that has specially hoarded the gold in its room/on its person compared to the same creature that spawned with those things already in place?
How will a standard enemy AI with one special ability learn/change in such a way that the player can tell the difference in the 5-10 turns it takes for that creature to be killed?
Sorry to be a downer, but the thing about interesting AI, sadly, is that it most often only ends up interesting from the back end.
Numeron makes a really good point here. One idea I have been toying with is to give little thought bubbles for characters and have symbol there to show what it is currently thinking of. Sort of like how Sims or Dungeon Keeper does it. It would give player better idea what's going on. One can also just fake it and have thought bubbles without complex AI and let player to think that the creatures are actually pondering stuff when they're just randomly walking around.
If the game has very complex mechanics behind the scene and player never notices them, they don't really matter. On the other hand, if the player thinks that the AI is doing something really clever and complex when it isn't, it's like an almost free feature. There was an article about this in Gamasutra, but I couldn't quickly find it.
-
And yet, it's possible to make AI interesting with pretty simple means. In fact, I think keeping it simple will make it much clearer to the player what's going on. Assigning sliders/values for stuff like "greed", "bravery", "anger" etc. is the kind of thing that sounds cool, but it is probably going to be too subtle. It might be a better idea to have something like "greedy" as a single trait that some critters have and other don't. In the original Rogue, for instance, orcs would always head over to pick up treasure. That kind of behaviour is instantly recognizable.
I get that you want something a bit more complex than that, but what I'm getting at is that hard and fast rules might be a better idea than weighing many subtle inclinations against each other. I do think it's a cool idea to have NPC and monster AI that brings the world alive with people doing their chores (farmers farming, cartographers exploring …) and killing time (going to the tavern, enjoying a game of cards), and can be influenced in different ways (an NPC who randomly hates canines will join you if he sees you kill a dog (but beware of being caught in the act by the owner), a carrion crawler can be lured onto a trap if you use raw meat as bait, etc).
Also, consider that these kinds of systems should affect gameplay in a fun and visible way. For example, a creature who goes around hoarding treasure might be uninteresting: it will mostly act of out the player's sight, and it results in levels where all the loot is in a single place, overriding your careful loot-distribution algorithm. A bit of pure flavor is ok, but direct your efforts towards stuff the player can use in some way. I remember this old platformer Abe's Odyssey, which featured a crablike monster that would chase (and instakill) the player, but which hated other monsters of the same type even more. So if you could lure two of them together on the same platform, they would ignore you for a while and start fighting between themselves. Flavor and tactics baked into one.
As always,
Minotauros
-
I just want to push back a bit on Numeron's notion that complex AI is often too complex for a player to notice. I think he's basically right for pure hack and slash. Here, monsters are basically just maniacal killing machines and charge or at their smartest hit and run. But MisterMoxxie here is suggesting a game with monsters and NPCs that are not always aggressive and who nevertheless move around and do things. Anyone who's played a few angband variants knows how ridiculous such actors can be without adequate attention to AI. Non-hostiles quickly reveal a lack of interesting AI.
edit: Another thing here is that Numeron suggests we should be designing AI not just to be discoverable (whoever heard of such a standard in the world of roguelikes?) but to be easily, instantly discoverable in the way that the mechanics of a smart phone game strive to be. But roguelikes should be full of hidden nooks and crannies. If a subtle AI allows weird, counterintuitive tricks, that's a good thing. If it takes a long time for players to realize that certain monsters are stealing all the gold on their levels, this is great.
edit II: On the other hand, the question of how you know what your fellow dungeon goers are doing is a good one -- but it has good answers. E.g. non-hostile animals would withdraw when approached and give warnings, like hisses or growls, if they're feeling crowded or cornered. Monsters could address such warnings and signs of aggression to other monsters. This is good grist for messages -- no need for thought bubbles or other fancy stuff, just "The monkey fighting snake hisses menacingly at the cave lemur."
-
If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery. Games are not simulations.
Likewise, FoV calculation that goes beyond determining current direct line of sight at max awareness distance from the player's PoV is a waste. LoS calcs should rarely be needed for AI purposes as the player-centric FoV map already has all the information needed. Given mutable terrain and procedural map generation, I can't see any value in more detailed treatments.
There seems to be some unfortunate trend in roguelikes recently that end up putting far too much effort into 'realistic simulation'. These high cost per mob AI implementations can easily lead to immersion breaking faults in actual game play. One example from a well known and popular game are vault rooms where a player's AoE spells are greatly reduced in effectiveness because it would slow down the game too much if mobs responded to an out of LoS attack. All vault mobs are ostriches with 'if I can't see you, you can't hurt me' immunity.
It is ironic that people who would never think of using a brute force solution to a low level problem, gladly employ brute force solutions such as simulation at the higher design level of modeling.
-
Wow, I'm glad to have so many different people in this discussion! Thanks, everyone, for your input! Lots of things I hadn't considered before. Taking all of your guys' ideas into suggestion, I think I'm going to shoot for a system that can produce 'complex' or 'smart' decisions, without actually being that complex under the hood.
I think using behaviour tags would be a great option, for a few reasons. The way that two or more tags would combine could be very interesting, and it also gives me a more direct way to communicate creature behaviours to the player. Maybe after seeing a creature with the 'greedy' tag take items off the ground once or twice, the player will have discovered that creature is greedy. Any time they [L]ook at that creature, or otherwise gather information, the 'Greedy' tag will now be displayed as well as other relevant information.
On the note of my original question, using FoV or LoS, I think I've got a much simpler solution that I'm going to test today on that, as well. By simply giving all creatures a 'sight' value, I can check that against the distance from monster x to object x. If it's 'out of sight' they obviously can't see it. In any case where a creature can't directly 'see' the object (ie it's behind a wall, etc), it could be assumed that the creature was previously aware of it being there. I may have to do something a bit different for viewing the player, to avoid the 'smarter' aggressive monsters from always ambushing them by knowing when they're coming, even when the player is out of view.
-
If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery. Games are not simulations.
This is a bit of a truism. I don't think anyone is talking about AI with no observable effects. Of course, it's important to take on board the criticism that complex/subtle AI can easily look indistinguishable from fairly mindless AI, as it seems people in this thread have.
Likewise, FoV calculation that goes beyond determining current direct line of sight at max awareness distance from the player's PoV is a waste. LoS calcs should rarely be needed for AI purposes as the player-centric FoV map already has all the information needed. Given mutable terrain and procedural map generation, I can't see any value in more detailed treatments.
There seems to be some unfortunate trend in roguelikes recently that end up putting far too much effort into 'realistic simulation'. These high cost per mob AI implementations can easily lead to immersion breaking faults in actual game play. One example from a well known and popular game are vault rooms where a player's AoE spells are greatly reduced in effectiveness because it would slow down the game too much if mobs responded to an out of LoS attack. All vault mobs are ostriches with 'if I can't see you, you can't hurt me' immunity.
It is ironic that people who would never think of using a brute force solution to a low level problem, gladly employ brute force solutions such as simulation at the higher design level of modeling.
I see two problems with this criticism: First, your example seems hard to attribute to excessive attention to AI. And indeed, the OP is asking about how to make smart AI cheap, so that what you're describing doesn't happen. Second, this general line of thought seems to lead to the conclusion that the perceived room for development of better AI in roguelikes is not really there and that inevitably new games will look substantially the same as existing ones in terms of AI. I doubt this is true, but if it is, it seems that we should just stick to nethack (or rather, porting nethack to smart phones).
I think too many people have played Dwarf Fortress and seen something inspiring for the idea that monster AI is pointless outside of the player's line of sight to be persuasive.
-
I see two problems with this criticism: First, your example seems hard to attribute to excessive attention to AI. And indeed, the OP is asking about how to make smart AI cheap, so that what you're describing doesn't happen. Second, this general line of thought seems to lead to the conclusion that the perceived room for development of better AI in roguelikes is not really there and that inevitably new games will look substantially the same as existing ones in terms of AI. I doubt this is true, but if it is, it seems that we should just stick to nethack (or rather, porting nethack to smart phones).
I think too many people have played Dwarf Fortress and seen something inspiring for the idea that monster AI is pointless outside of the player's line of sight to be persuasive.
This is impossible to respond to as I did not state anything that you claim.
-
Of course you didn't state anything that I claim. Maybe you meant you didn't state anything that I claimed you did. In that case, a more substantive response might include what you perceive those claims to be and how my perception is mistaken.
Anyway, I'm content, as you seem to be, to carry on as if you hadn't claimed anything at all. It's not impossible to respond to someone who prefers to defensively claim not to have said this or that rather than offering clarification or responding to counterpoints, but it's not often worth the time.
-
I know of two games which have really smart AI, but I don't know how expensive it is in terms of calculations:
1. Sil
2. Incursion
-
Regarding the graph-like data structures: One major beef I have with them is that if you start digging and changing your level, it's a PITA to rebuild. Also in some cases (caves, town), it's completely unintuitive how would you go generating the graphs.
An alternative would be organizing your data in a spatial hierarchy. The simplest that I can think and I'm planning to implement is a quadtree, as it requires zero storage cost for the nodes - every cell at every level can be derived implicitly. The costs will pretty much be updating the hierarchy when stuff moves, but if you restrict the number of levels (e.g. each node has a 4x4 subgrid of children) the costs will reduce.
-
If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery. Games are not simulations.
This is a bit of a truism. I don't think anyone is talking about AI with no observable effects. Of course, it's important to take on board the criticism that complex/subtle AI can easily look indistinguishable from fairly mindless AI, as it seems people in this thread have.
I'm with mushroom patch on this. Games are simulations. Perhaps abstracted simulations, but simulations still. The reason you have mana and hit points, is because your simulation is at a higher level and it's easier to design and program.
One of the things that people love about Incursion and want to see more of, is the non-observed behaviour. They mention loving seeing signs that other life is going on in the dungeon. Now Incursion has that behaviour happening as if the player was there, but that is irrelevant and is the easy way to do it. Harder and more optimal would be abstracting it, and doing so would lessen the chance of the effect seen by the player being believable. Simulating is something games do not do enough of, and for good reason.
-
Regarding the graph-like data structures: One major beef I have with them is that if you start digging and changing your level, it's a PITA to rebuild. Also in some cases (caves, town), it's completely unintuitive how would you go generating the graphs.
An alternative would be organizing your data in a spatial hierarchy. The simplest that I can think and I'm planning to implement is a quadtree, as it requires zero storage cost for the nodes - every cell at every level can be derived implicitly. The costs will pretty much be updating the hierarchy when stuff moves, but if you restrict the number of levels (e.g. each node has a 4x4 subgrid of children) the costs will reduce.
Yeah, anything you precompute may need to be recomputed to some degree with updates. (As an aside: In my opinion, many roguelikes go way overboard with cheap digging -- too fast, sometimes instantaneous with spells and wands that are easy to get, few limitations, etc. I mean, we're talking about excavating a volume of earth, often solid rock, measuring 5'x5'x8' or so for each tile, in other words, many, many tons of material...) In this case, though, I don't think the graph I've described needs to be rebuilt, just updated. But, sure, you'd need to write a bit more code to cover alterations to the dungeon.
-
One of the things that people love about Incursion and want to see more of, is the non-observed behaviour. They mention loving seeing signs that other life is going on in the dungeon. Now Incursion has that behaviour happening as if the player was there, but that is irrelevant and is the easy way to do it. Harder and more optimal would be abstracting it, and doing so would lessen the chance of the effect seen by the player being believable. Simulating is something games do not do enough of, and for good reason.
Sorry about the double post, but I'm supposed to be writing a research statement, which means I'm in procrastination overdrive. I think this is right, although I'm not sure I get what's being said in the last two sentences. I agree with others in the thread that there are serious issues with designing a game as just a slice of a larger simulation, particularly performance related ones. On the other hand, simulation is great for creating flavor, depth, and realism (whatever that means in the context of the game). The answer seems to be finding ways to cheaply approximate simulation.
-
One of the things that people love about Incursion and want to see more of, is the non-observed behaviour. They mention loving seeing signs that other life is going on in the dungeon. Now Incursion has that behaviour happening as if the player was there, but that is irrelevant and is the easy way to do it. Harder and more optimal would be abstracting it, and doing so would lessen the chance of the effect seen by the player being believable. Simulating is something games do not do enough of, and for good reason.
The difference between computer simulations and computer games is subtle but important. At the core, the distinction is that simulations are about things (or systems) and how they behave, and games are about a fun user experience.
When I said: "If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery.", the pure randomness or other simple fakery portion refers to creating the illusion of some complex behind the scenes simulation. I disagree that faking is somehow more expensive or harder than running a real simulation.
Lets put this in a context we can all see and understand; a persistent dungeon level which a player returns to after N number of turns. There are three approaches to handling this:
1) Ignore it and revive the level just as it was.
2) Run N turns of simulation to bring the simulation and the player frames of reference into sync.
3) Fake 2 by a simple yet intelligent application of randomness.
I believe approach #3 is preferable because it is simple to implement in terms of programmer effort, less demanding of resources especially as N increases, and largely indistinguishable from the observable results of #2.
If I understand you correctly, I believe we really only differ on the level of abstraction. The higher the level of abstraction you apply to approach #2, the more it becomes approach #3. You can run an immensely detailed simulation, but if I as a player see only a small edge of it, it is largely wasted.
Bringing this all back around to the OP's questions; The less abstract simulation is the more expensive the AI implementations become. Consider that for a detailed simulation you treat the mobiles as Actors who are indistinguishable from players except for source of control input. They have their own FoV maps, complex decision making, pathing, etc, which runs every turn regardless of whether they are close to the player or on the far side of the map. Yes you can try to make this less expensive by caching various precalculations and deciding what mutations of the game state require recalculation of which portion of the various caches. I believe this is needless complexity compounding the original design error.
Alternatively, doing minimal calculations - extending and reusing the player's FoV, you can easily predict what mobiles will be observable within a move or two. At the point of transition between observable and non-observable you can apply whatever effects you like to make it look like some larger events have occurred behind the scenes - the wounded mobile stumbles into view. The simulation backstory takes place in the player's mind just as it would if you truly ran a full sim. If you desire the appearance of a larger encompassing simulation, you can track the observed 'faked' simulation events and weight future abstractions by them.
In other words, if you truly must have a simulation running in the background, abstract it to the highest degree you can get away with and keep it as separate from the AI as you possibly can. Spend the cycles you have regained on smarter decision making when you need it. The most sophisticated simulated world you could possibly run will be rarely glimpsed by the player, the responsiveness of the game and the presence or absence of unintuitive limitations and unexpected behaviors are far more noticeable.
-
When I said: "If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery.", the pure randomness or other simple fakery portion refers to creating the illusion of some complex behind the scenes simulation. I disagree that faking is somehow more expensive or harder than running a real simulation.
Lets put this in a context we can all see and understand; a persistent dungeon level which a player returns to after N number of turns. There are three approaches to handling this:
1) Ignore it and revive the level just as it was.
2) Run N turns of simulation to bring the simulation and the player frames of reference into sync.
3) Fake 2 by a simple yet intelligent application of randomness.
I believe approach #3 is preferable because it is simple to implement in terms of programmer effort, less demanding of resources especially as N increases, and largely indistinguishable from the observable results of #2.
If I understand you correctly, I believe we really only differ on the level of abstraction. The higher the level of abstraction you apply to approach #2, the more it becomes approach #3.
Yes, for the most part that is correct. Where it isn't correct, both here and for the rest of your post, is that you seem to portray a level of simulation as an either/or choice.
A ticked simulation (approach #2) where AI/NPCs are all modelled the same way as the player, can be more expensive -- but only if you do it badly. And in the same way, a higher level simulation where (approach #3) AI are modelled in a simpler way, can be just as expensive -- but only if you do it badly.
I also suggest that you can have different levels of abstraction, with parts that matter using modelling and parts that don't using fakery. And that you can dynamically switch in different levels when it matters. Also there are umpteen games where player's have started playing and talked amongst themselves saying "wow these NPCs are really smart", but after a while the fakery becomes apparent and obvious.
Your post is long and full of claims, most of which are simplistic and not necessarily true. I suspect that you have a way you like to make games, and you shape your posts around it. You're welcome to it, as is whomever chooses to adopt your your positioned views.
-
Lets put this in a context we can all see and understand; a persistent dungeon level which a player returns to after N number of turns. There are three approaches to handling this:
1) Ignore it and revive the level just as it was.
2) Run N turns of simulation to bring the simulation and the player frames of reference into sync.
3) Fake 2 by a simple yet intelligent application of randomness.
I believe approach #3 is preferable because it is simple to implement in terms of programmer effort, less demanding of resources especially as N increases, and largely indistinguishable from the observable results of #2.
If I understand you correctly, I believe we really only differ on the level of abstraction. The higher the level of abstraction you apply to approach #2, the more it becomes approach #3. You can run an immensely detailed simulation, but if I as a player see only a small edge of it, it is largely wasted.
I mostly agree with this, with a clarification you may well be attempting to imply.
Whether you go with 2 or 3 is an implementation detail, the important distinction is whether your system is one that makes sense to the player. For example a basic distinction is whether the scrambling of the level respects conservation of stuff. If you add or remove monsters and items, you're making a particular choice along the realism axis. Personally I prefer to emphasize realism, so I'd generally limit myself to moving non-consumable items around and having monsters consume consumables, but discarding that to enable a particular style of game is also a valid option.
Regarding FoV, to be concrete about how you would "cheat" with monster vision. You can simply store references to things monsters are interested in on a convenient data structure, cull for distance, and check visibility of the items directly. It would rarely be rewarding to do a full FoV calculation for a monster, the player is a special case due to rendering more than anything else. In that special case you're required to determine visibility of relevant and irrelevant alike since it will bother the player if it's inconsistent, hence the need for FoV precalculation.
There are probably circumstances where a monster might want to check visibility of enough things that FoV calculation is the cheaper alternative, but I can't think of one.
-
there's also the actual code element to this:
It is simple to say "Monster check FOV for interesting things".
The code for it would depend on how you are storing things - lets assume a single monster, a list of items with their location or are items stored in the map list.
code:
for each item check if in view range
if in view range check if in view (walls would prevent seeing)
that is fine for a small number of items, but becomes intensive for large numbers of items and also large numbers of monsters. you really need a solution that does it in the fewest possible steps.
FOV by tiles is very expensive..
-
Regarding FoV, to be concrete about how you would "cheat" with monster vision. You can simply store references to things monsters are interested in on a convenient data structure, cull for distance, and check visibility of the items directly. It would rarely be rewarding to do a full FoV calculation for a monster, the player is a special case due to rendering more than anything else. In that special case you're required to determine visibility of relevant and irrelevant alike since it will bother the player if it's inconsistent, hence the need for FoV precalculation.
That's a nice idea and works well with sparsely distributed "things" in a map (other AI actors, items, doors, features, whatever) -- the sparser the things of interest are, the more the value over direct FoV calc. You still need to cheat differently for monster path planning, as the "wall-or-floor" data is dense (assuming every tile has the walkable flag set or sth similar). Unless you assume monster knowledge of the map, of course.
-
Path planning shouldn't require cheating. A single computation, while potentially expensive, yields enough information for many turns of movement if you're using the usual algorithms...
-
I don't see a good reason to not give the monster full wall data unless the player is manipulating it, and even then, you treat the player modifications as an exception rather than doing FoV for everything.
-
Path planning shouldn't require cheating. A single computation, while potentially expensive, yields enough information for many turns of movement if you're using the usual algorithms...
Well, path planning for every single monster using each monster's proper visibility (history of what has been visible, what's currently visible) can get quite expensive... unless you have 5 monsters on the map or something, you know a magic algorithm that does the above and I do not.
-
Path planning shouldn't require cheating. A single computation, while potentially expensive, yields enough information for many turns of movement if you're using the usual algorithms...
Well, path planning for every single monster using each monster's proper visibility (history of what has been visible, what's currently visible) can get quite expensive... unless you have 5 monsters on the map or something, you know a magic algorithm that does the above and I do not.
I fail to see what monster vision has to do with pathfinding. Do you decide how to get places based only on what you can see at the moment? I know I don't. Monsters live in dungeons. Assuming they have perfect information about dungeon layouts is totally reasonable and realistic.
Unless you're programming for a PDP-6, running something like A-star on average once per 10 monster turns (and remember, turns are probably not the smallest subdivision of time in a reasonable roguelike) with 100 or so monsters isn't going to cause your magnetic cores to catch fire.
-
I fail to see what monster vision has to do with pathfinding. Do you decide how to get places based only on what you can see at the moment? I know I don't. Monsters live in dungeons. Assuming they have perfect information about dungeon layouts is totally reasonable and realistic.
Unless you're programming for a PDP-6, running something like A-star on average once per 10 monster turns (and remember, turns are probably not the smallest subdivision of time in a reasonable roguelike) with 100 or so monsters isn't going to cause your magnetic cores to catch fire.
Come on, ditch the same old story for a second, you might want to create some AI that tries to explore the dungeon like you, part of a team or not. Perhaps you're making hunger games the roguelike and all your 100 players need to have fair vision. I'm talking about the few cases (not all monsters everywhere in the game) that you want to have fair vision for exploration. My bad for using the term monster for that.
Anyway, so yeah referring to A* with known layout, sure that's easy and fast.
-
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'm curious, outside the "hunger games" like scenario, where are you envisioning using fair exploration?
-
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.
-
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.
-
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.
-
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.
-
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.
-
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: (http://i57.tinypic.com/20l0z9g.png)
And as the storage is dense, it is independent of your map (dungeon, overworld, cavern, whatever)
-
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.
-
Eliminated a single redundant bit above, 1 bit less required, half the storage cost needed.
-
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.
-
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.
-
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.
-
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.
-
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.
-
And, thinking some more (a dangerous pastime, I know)...
Suppose we were to store at each tile a bitmap of which other tiles within sight radius from it are visible. With sight radius of 15, that would be about 500 bits per tile because any pair of tiles can use mutual visibility mapping for the leftmost of them, or the uppermost if they're in the same column; that way you only need bits for half of the 31x31 tiles under consideration.
Now this is a factor of about 8 bigger than what I'm using for FastLOS, but it's a lot more straightforward to calculate and has an additional advantage of requiring storage that scales linearly with increasing area rather than with the square of increasing area.
-
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.
I think it's hard to analyze what the asymptotic storage requirement really is because it depends on local geometric properties of the map that might be hard to get a handle on. What I meant by "reasonable" maps is pretty much exemplified by the maps reaver uses: rooms not much bigger than 15x15 connected by narrower corridors. I assume your 'n' here is the number of non-wall tiles. In that case, I think for "reasonable maps" the storage requirement is closer to O(n). (Obviously, for a totally open map, it will be O(n^2).)
I mean, the silliest thing you could do is just take an array A[x_1, y_1, x_2, y_2] with four axes representing (x_1, y_1) and (x_2, y_2) for all pairs of points and record a boolean value in each element for line of sight. This would surely be faster than anything involving computing hashes (like a Bloom filter), but the memory cost is like O(d^4), where d is the diameter of the map. But then you say, wait, all the stuff we care about is in the part of this thing where (x_1, y_1) is close to (x_2, y_2). Now say s is the average number number of squares viewable from any given square -- this is a geometric quantity associated to a "reasonable" map generation algorithm. Then your storage cost with just throwing all the mutually viewable pairs into a constant time access collection depends on your storage cost for the collection -- this should be O(p) where p is the number of pairs. Obviously, p = sn, so what we have is O(sn).
I guess my core claim, which obviously I'm not going to carefully formalize or prove, but I think it should be intuitively clear, is that s does not depend on a particular map, but only on the generating algorithm if the algorithm is "reasonable." In particular, making a bigger or smaller map with the same algorithm will result in roughly the same s. In this sense, your storage cost is actually O(n) for a given algorithm.
-
Suppose we were to store at each tile a bitmap of which other tiles within sight radius from it are visible. With sight radius of 15, that would be about 500 bits per tile because any pair of tiles can use mutual visibility mapping for the leftmost of them, or the uppermost if they're in the same column; that way you only need bits for half of the 31x31 tiles under consideration.
Now this is a factor of about 8 bigger than what I'm using for FastLOS, but it's a lot more straightforward to calculate and has an additional advantage of requiring storage that scales linearly with increasing area rather than with the square of increasing area.
Yeah, my feeling is that this would be less storage efficient than using a Bloom filter on mutually viewable pairs with .1% false positives (~16 bits per mutually viewable pair, does not actually store the pairs), but much faster on look-ups. With a maximum radius of 15, I think most of the pairs that will be represented in your data structure will not be mutually viewable (again, for a "reasonable" map).
-
Bear, thanks for the extra explanations of the FastLOS, I'll check it out when I have a bit more time, at the moment I'm trying to finish testing of the bit-fiddled brute force method that we were mentioning about.
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.
Suppose we were to store at each tile a bitmap of which other tiles within sight radius from it are visible. With sight radius of 15, that would be about 500 bits per tile because any pair of tiles can use mutual visibility mapping for the leftmost of them, or the uppermost if they're in the same column; that way you only need bits for half of the 31x31 tiles under consideration.
Now this is a factor of about 8 bigger than what I'm using for FastLOS, but it's a lot more straightforward to calculate and has an additional advantage of requiring storage that scales linearly with increasing area rather than with the square of increasing area.
Wait, wait, there might have been some confusion, the costs with the tile pair storage would not be as you suggest. For a 100x100 map with 15 max sight radius, the costs would be 2^N bits, where:
N = mapIndexBits + 2*sightRadBits +1 (1)
mapIndexBits = the number of bits needed to represent the linear map index. For 100x100 = 10000, and 10000 < 16384, so:
mapIndexBits = 14
sightRadBits = the number of bits needed to represent the sight radius. For 15, 15 < 16, so:
sightRadBits = 4
So, if you plug the numbers above in eq. (1), you'll need 23 bits, which means 2^23 = 1 MB of storage. With this 1MB you can store up to a 128x128 map with 15 max sight radius. By now, you might be ask where does eq. (1) come from.
Now as I said in one of the previous post, when you want to store a pair of points, you can do:
* sort the points by the X axis
* store the first point's linear index in the mapIndexBits ( linear index is "point.x + map.width*point.y")
* store the second point's offset to the first point in the rest bits. The offset in X is ALWAYS positive or 0, so sightRadBits will suffice. The offset in Y needs one more bit for the sign. And that's why its "2*sightRadBits + 1" in eq. 1.
The costs for updates are also very nice: if you update a few tiles, you would just need to run the FoV algorithm in these tiles:
for each tile in updated_tiles:
view_points = points_in_radius(tile, max_sight_radius) // get all points in the given radius, centered on tile
for each vpoint in view_points:
is_visible = LineOfSight(tile, vpoint) // Calculate line of sight with your fav fov
set_precalc_los_bit( tile, vpoint, is_visible) // update our dense precalculated-LoS map
-
Ok, some results. The test is as follows: I generate a standard dungeon map with the specified dimensions, I place an actor somewhere random, I set his LoS range and let him autoexplore. The test is over when all tiles have been explored. I use two methods to calculate FoV:
Old: run recursive shadowcasting
New: for each tile in the FoV radius, test visibility using the precalculated map.
Code is in C++
Laptop is an i7 @ 2.5 Ghz , Desktop is a Xeon @ 2.6 Ghz.
Los is the los radius
There are three numbers:
1. total number of milliseconds for the visibility calculation
2. total number of turns
3. milliseconds per visibiliy calculation (average)
------------------------------------------------------------
Laptop
Los: 7
80x25
New: 6.44531 - 342 : 0.0188459
Old: 13.7655 - 346 : 0.0397846
160x50
New: 27.361 - 1303 : 0.0209984
Old: 50.5674 - 1304 : 0.0387787
320x100
New: 138.124 - 5267 : 0.0262245
Old: 218.997 - 5356 : 0.0408881
--------------------------------
Desktop
Los: 7
80x25
New: 2.26241 - 342 : 0.00661523
Old: 5.72091 - 346 : 0.0165344
160x50
New: 9.13756 - 1303 : 0.00701271
Old: 22.3549 - 1304 : 0.0171433
320x100
New: 44.7344 - 5267 : 0.00849333
Old: 94.1606 - 5356 : 0.0175804
----------------------
Desktop
Los : 15
160x50
New: 26.1644 - 1188 : 0.0220239
Old: 25.9351 - 1178 : 0.0220162
Los : 4
160x50
New: 5.26167 - 1835 : 0.0028674
Old: 22.4202 - 1836 : 0.0122114
--------------------------------------------------------
Interpretation:
Well, for FoV calculation where you do LoS with each tile, the benefits reduce as the bottleneck shifts to the "for each tile" processing.
If you have LoS calculations as described earlier in the thread ( for each interesting entity in a given radius, run LoS), it can be very,very beneficial.
What annoys me is that I have a bug somewhere as the bot uses a different amount of turns to complete the autoexplore, even if I start with the same seed. Anyway, I don't have time to check that now.
-
Hm, I'm not sure I get your test. So you're checking field of view by iterating over all squares within the given radius and checking line of sight to the current location and using this data to autoexplore? It seems like a practical use case, but I'm not so sure about calculating the full field of view on each move. Do I have this right?
What I had in mind was more of a pure test of the speed of the LoS check: Just pick a non-wall square and another non-wall square within the LoS radius (randomly in both cases) and check whether they're mutually viewable in the usual way vs. in the precomputed/cached way. It sounds like you're saying caching gives ~2x improvement over more obvious line of sight checks (which is not as good as I was hoping for, actually, but not bad) in terms of raw speed. Is that right?
-
Hm, I'm not sure I get your test. So you're checking field of view by iterating over all squares within the given radius and checking line of sight to the current location and using this data to autoexplore? It seems like a practical use case, but I'm not so sure about calculating the full field of view on each move. Do I have this right?
Yes. I have not implemented a very smart/progressive fov calculation, but my dumb fov uses LoS a lot which is the purpose of fitting that into the test.
What I had in mind was more of a pure test of the speed of the LoS check: Just pick a non-wall square and another non-wall square within the LoS radius (randomly in both cases) and check whether they're mutually viewable in the usual way vs. in the precomputed/cached way.
The test you suggest is quite easy to implement, will try it. I would expect massive difference in speed. I did not try it because it's not going to be a real test case, but I guess it'll serves its purpose.
It sounds like you're saying caching gives ~2x improvement over more obvious line of sight checks (which is not as good as I was hoping for, actually, but not bad) in terms of raw speed. Is that right?
Yes, when you calculate FoV using "for each tile within radius, calculate LoS".
-
I guess my question is about the comparison of this precomputation business versus a line of sight algorithm (something like: compute a discretized version of the line connecting two points and check whether there's an obstruction any of the squares in that approximation). It's not at all clear to me which of these two should be faster on average -- I guess we should expect to see more LoS computations between points near the maximum line of sight difference, which works against the conventional LoS algorithm, but I don't have much intuition for how fast C++ maps are.
-
There is an important difference between line of sight and field of view, for most algorithms.
If you're working directly with map geometry, it's always more efficient per tile to calculate field of view (ie, to derive the whole set at once of tiles to which line of sight exists) than line of sight.
This is because when you're doing field of view using one of the best-in-class algorithms like spiral-path or recursive-shadowcasting, it takes O(1) to add each tile to the set, working from the geometry of the map. But if you're computing line-of-sight for a single square, the map-based algorithms are O(n) where n is distance, because you have to visit every square between the origin and the target to make sure your view isn't obstructed by map geometry along the way.
So if you're doing field-of-view well (one of the best in class algorithms) FastLOS should change the time required for field-of-view by a constant factor - probably less than 1 (meaning faster) but it depends on your implementation.
If you're doing field of view badly, by calculating line-of-sight to every tile iteratively, you should expect switching to FastLOS (or spiral-path, or recursive-shadowcasting) to give you a speedup that scales proportional to your sight radius times a constant. But no matter what map-based algorithm you're using for line-of-sight, switching to FastLOS (or any constant-time access to precomputed LOS information) should give you that same proportional speedup on that task.
What a method such as FastLOS (or any of the variants we've been discussing here) does, is give you access to precomputed LOS information in O(1), which is the same as the best map-based algorithms can get it when they're doing field-of-view. If you're doing Field of view, FastLOS is therefore on the same order of complexity (but likely a constant factor faster depending on implementation details) as Spiral-Path or Recursive-Shadowcasting. But if you're doing Line of Sight, you're getting O(1) where a classic LoS algorithm would give you, at best, O(n) where n is the number of tiles separating origin and target.
-
Yeah, that's not really what my question is about. If what you want to do is calculate LoS here and there for deciding if something can hit something else with a spell or missile weapon, then obviously an LoS computation will be faster than FoV. Yes, LoS is O(d), but FoV for the same purpose is O(d^2) in the worst case. Reaver is talking about using C++ map data structures (which I think are implemented as red-black trees -- so O(log n) access time) to store mutually viewable pairs for LoS testing. My question is whether, in practice, reaver's map based implementation is actually faster than LoS and what the difference is. I don't think this is immediately clear. We're not talking large values of d here (maybe large values of n though). It depends on the map data structure, which is something I don't know the specifics of performance-wise.
-
As far as I know there is no performance guarantee for the C++ map data structure. Given its ordering constraints, and assuming the people who wrote your stdlib are either sane or interested in efficiency, you're probably right about it being implemented as a red-black tree and thus having O(log n) access.
But the ordering constraints are useless in this case so you should be using an unordered map. Unordered maps are implemented as hash tables, thus O(1) access.
-
There is an important difference between line of sight and field of view, for most algorithms.
If you're working directly with map geometry, it's always more efficient per tile to calculate field of view (ie, to derive the whole set at once of tiles to which line of sight exists) than line of sight. ...
I know, my Fov might be suboptimal, but I didn't want to demonstrate my FoV algorithm. I was just showing that even with FoV, using the precalculated LoS for every square is faster. I expect that comparing bresenham LoS to the precalculated one presented here will be day and night.
Reaver is talking about using C++ map data structures (which I think are implemented as red-black trees -- so O(log n) access time) to store mutually viewable pairs for LoS testing. My question is whether, in practice, reaver's map based implementation is actually faster than LoS and what the difference is.
No, no, nobody reads? it's DENSE, no map data structure, just a biiiiig bit buffer where you encode/decode the pair location/offset as an index, and the visibility is the bit value. It's guaranteed to be faster than anything else you throw at it, unless it's faster than some mul/adds and bitops, which I kinda doubt. Damn it, I'll do that LoS test to show you the speed diff.
-
No, no, nobody reads? it's DENSE, no map data structure, just a biiiiig bit buffer where you encode/decode the pair location/offset as an index, and the visibility is the bit value. It's guaranteed to be faster than anything else you throw at it, unless it's faster than some mul/adds and bitops, which I kinda doubt. Damn it, I'll do that LoS test to show you the speed diff.
Eggs Ackley. Reaver and I have been talking about bitbuffers. Others have been talking about more complex constructed data such as maps, lists, bloom filters, etc.
There are good reasons, as Reaver just pointed out, to use bitbuffers if you can make them work for your needs. If you can get them packed appropriately, there is hardly any way to get anything faster. The FastLOS sight mask is a specialized little bitbuffer; I work hard during map generation to get the sightlines boiled down to where I can check them using binary AND.
-
Questions from the peanut gallery:
1) What impact does opening/closing a door (removing or adding obstacle) have?
2) Can these structures be lazy initialized or is precalculation a requirement?
3) Assuming full exploration is best case use scenario, what is the worst case use scenario and
what performance gain over standard fov algos can be expected there?
-
Questions from the peanut gallery:
1) What impact does opening/closing a door (removing or adding obstacle) have?
2) Can these structures be lazy initialized or is precalculation a requirement?
3) Assuming full exploration is best case use scenario, what is the worst case use scenario and
what performance gain over standard fov algos can be expected there?
1) In my case: you calculate the FoV from that tile with your favorite algo and set the fov bits with visible/not visible. So around 50 bit buffer accesses
2) Could be lazy initialized, but precalculation makes more sense. In my case, the precalculation amounts to running the fov algo from every single point
3) full exploration is not the best case scenario. It's just one that I chose! Again, as bear said, you won't see the massive differences in FoV calcs, but in LoS checks.
Anyway, some stats:
values are milliseconds for the total time for...
for los values from 3 till 15 do 1000000 random pair checks, where the pairs have distance <= los
Bresenham is Los with ... bresenham.
Precalc samples from the bitbuffer
null calculates the time to read the pre-generated random pair lists, and is used to calculate the "base cost" before doing any algorithm work.
80x25 map
Bresenham: 3790.5
Precalc: 570.626
null: 179.297
----------------------------------------------------
160x50 map
Bresenham: 4229.73
Precalc: 608.415
New: 131.031
----------------------------------------------------
320x100 map
Bresenham: 4676
Precalc: 714.562
null: 129.874
---------------------------
So, the above says that using the precalculated bitbuffer is about 6.6x faster than calculating LoS using bresenham. For what is worth. I think it's now time to move on to coding something more useful.
-
Ok, feeling stupid, consider:
1..#...
#..#.2.
3..+...
...#...
Now if I understood your explanation correctly, opening the door ('+') would mark cells 1, 2, and 3 as visible. Yet even with the door open, 1 and 3 are not visible to each other and neither is 2 visible from position 1. I'm missing something.
I thought that, working with pairs, you'd have to recalc everything that can see beyond the door as well as the door itself?
-
Ok, feeling stupid, consider:
1..#...
#..#.2.
3..+4..
...#...
Now if I understood your explanation correctly, opening the door ('+') would mark cells 1, 2, and 3 as visible. Yet even with the door open, 1 and 3 are not visible to each other and neither is 2 visible from position 1. I'm missing something.
I've added '4', to make an additional point.
By opening the door, the way I described it above, you will only update pairs that have (+) as one of their points. So, (1,2), (2,3), (1,3) etc are not gonna change. But as you can see, my assumption that the update only needs to calculate a single FoV is wrong, as (3,4) is now visible, where it was not before.
So, as a correction, in order to do a proper update, if (+) changes its obstacle status, we update the bitbuffer as follows:
for each point 'p' around '+' with distance to '+' < maxSightRadius
p_disk = all points around 'p' with distance to 'p' < maxSightRadius
for each point 'p2' in p_disk:
is_visible = LoS(p,p2)
store_to_bitbuffer(p, p2, is_visible)
So updates are costlier, but not massively so. Unless you have a really big maxSightRadius
-
Makes sense now, thanks :)
-
Thanks again, reaver. Interesting data.
-
Fascinating stuff, unfortunately I suspect DDA is a pathologically poor fit for this algorithm :(
Max view distance is 60
Mostly open environments.
Partial obscuration.
Don't care much about monster vision.
Maps are tiled, so we'd need to shift and partially regenerate the cache frequently.
Frequent visibility changes (smoke and other obscurants)
Special reasons*
The side issue of complexity of doing bresenham to all tiles reminded me I had generated this while looking into it previously: https://gist.github.com/kevingranade/5153746 and related https://gist.github.com/kevingranade/5678549
The number is the number of visits to each cell when drawing a line to each point on the border. Obviously this was unacceptable, as it had terrible artifacts in addition to being not all that fast. It's a pretty pattern though ^_^
In the end I went with a recursive shadowcasting algorithm. You've reminded me I've been meaning to bit-pack the working data for that, the overhead of the additional addressing operations is nearly guaranteed to be trivial compared to being able to fit more of your working set in cache.
Don't forget, your working set for a very fast algorithm should fit in your processor's data cache, not just ram.
For general data, don't worry about it too much, but if you're iterating over something a LOT, saving bits matters.
*Post coming soon about an interesting FoV hack I pulled off in DDA
-
Fascinating stuff, unfortunately I suspect DDA is a pathologically poor fit for this algorithm
...
Indeed, it's as bad a fit can be from your requirements. For such larger grids, you'd be better of with multi-resolution grids. Or I'd start looking what RTS games do, where they have even larger grids and view distances
*Post coming soon about an interesting FoV hack I pulled off in DDA
/popcorn
-
Indeed, it's as bad a fit can be from your requirements. For such larger grids, you'd be better of with multi-resolution grids. Or I'd start looking what RTS games do, where they have even larger grids and view distances
Here's another can of worms: Has anyone ever tried to do line of sight/field of view in a roguelike using binary space partitions in two dimensions the way the DOOM engine did? I've always thought you could get a lot of milage out of this approach if you're dealing with large, complex rooms. Should be pretty damn fast. On the other hand, it's a pretty complicated undertaking to code something like that.
(In particular, this would involve a non-grid based internal map representation, with walls defined by line segments, etc.)