That would provide a good start, but my algorithm really cares about whether there's line of sight, or whether there's some path the sound would travel before reaching the player. Strength of the event is determined by the path taken, and even the same path travelled twice does not need to yield the same result (a door might've been closed, a smoke grenade might've exploded, a barricade erected, etc.). This is all by design.

To get the same effect starting with a list of interested characters, you would need to apply path-finding between the location of the character and the origin of the event. Path finding in the worst case (when the character and origin cannot be connected) will actually be slower than the propagation algorithm. Doing path finding individually for all possibly affected characters will for sure yield worse results.



Nonono, don't claim that the design of my algorithm is an accidental implementation detail. At this point either your argument is dishonest, or you're insulting me by thinking I would not stop to think before writing the algorithm.

Yes COBOL is still widely used, however, most of the world's banking transactions are done using IBM's IMS.
IMS is a hierarchical database and was one of the first databases IBM created.
The backend storage is VSAM, which is roughly similar to the various DBM on Unix.

I think this is an interesting case, so I made a test to do exactly this. I made a FloodEvent that would append a "flood message" to the description of all the 10,000 rooms (probably if you really want something like this you would use something like a waterLevel property on the rooms, rather than modifying the description, but for the test this will suffice).

The event was now completed within 30ms. But that's not the whole story as the modified objects still had to be pushed to the sync thread before the next event may be handled by the game thread. Pushing 10,000 objects to the other thread took 250ms. So modifying 10,000 objects at once is going to give me a total cost on the game thread of 280ms. A very good score I think. Of course, after those 280ms it still took a few seconds for all the changes to be written to disk (I'm using a 3 year old workstation, no SSD), which means if events as heavy as this example occur every second the sync thread would not be able to keep up. Of course a hickup in the game thread of 280ms is already noticeable by players, but if it happens only very rarely I guess nobody would pay attention. All in all a nice experiment :)

Update: Using the profiler I actually discovered some inefficiencies in the copy process for pushing modified objects to the sync thread. I've made some small optimizations, and the event can now complete in <25ms and the copying in <150ms :)

Honestly, it goes back to "what is good enough". Will a player have any idea if the flood event took 20 seconds to complete vs 30ms? Especially if you're not blocking during this event, the time to propagate a flood event over a very large area isn't very important as long as it happens reliably.

Again, I think we're focusing on the things that don't matter.

Hehe, this is definitely a side-track yes. But the game thread would block for 280ms, so that is surely noticeable, and reducing it to 175ms is certainly a good thing. If only I had a use case for actually flooding 10,000 rooms :D

I'm sure it's not accidental. Algorithms and data structures are tightly linked, but they are implementations that attempt to satisfy requirements.

Given these requirements:

Why did you choose to represent virtual space in your mud as a collection of rooms and exits?

Is there a significant difference with other models? If you go roomless you'll end up having to add algorithms to create room-like behavior (or your mud will be lame) if you go for rooms you'll end up having to add algorithms to create room-less behavior (or your mud will be lame).

A hybrid model might be preferable where a room represents a 3x3 or 5x5 grid, which would allow some degree of spatial movement within a room, while still being able to treat rooms as single units.

As someone who spent the majority of his time on something that is mostly classified as "room-less", this is flat out wrong. Exhibit A: http://frontiermux.com/page.php?3

Rooms are not a requirement, and aren't always optimal. While we may have been "lame" to some, we regularly averaged 90+ connected at peak in the not-too-distant past (prior to the staff moving on).

There is life outside of rooms, and the alternatives don't necessarily even have to resemble a traditional room-based game.

Let me clarify, the moment you add obstacles you begin modeling room-like behavior. If in Frontier you float around on an empty 2d plain without obstacles and you shoot at anything that moves within range, then yes, I would call this lame. If you have to target (like in WoW) and click the fireball button repeatedly, then it's even lamer, though WoW does model room-like behavior to a small extend.

Disagree with this as well. We had terrain with varying elevations, with some elevation changes being too much for certain kinds of vehicles to traverse, but these formations and elevation differences were varied and rarely separated the map into something you could even begin to think of as a "room".

Again, rooms are not a requirement, and are not always even desired.

Let's be clear, most muds withrooms implement the barest minimum of room-like behavior.

I'm rather curious why Arend went with rooms as well given his gameplay goals.

Depending on the definition you could argue that a room constitutes your line of sight, in which case all that Frontier accomplished is that they got rid of exits, and called it an improvement. I guess a mud technically does not need closeable exits, though I'm not sure how it would be undesirable.

And if you add the modeling of exits in a roomless world, what are you going to call them? North, East, South, West? Then you're back to square one. You may as well add the room/exit model and save yourself the trouble of having to figure out if there is an exit leading in a given direction, and what to call it.

The ability to move 1 foot at a time in any given direction is somewhat over rated in my opinion as it's the restriction of options, opposed to no restrictions, that creates gameplay.

My main issue with the roomless design is that it only appears to complicate things, to such an extend that worlds are left bare and featureless, empty deserts of infinite space with little content.

Honestly, Scandum, it sounds like either you don't have good ideas for how a roomless game should work, or haven't really played on any that you've liked.

I don't think your arguments about line of sight being a "room" are at all founded, since line of sight does nothing to delimit interactions. LOS merely means that you are aware of another object. It need not be mutual, and you don't even necessarily have to have LOS to interact with other objects (artillery based on locations fed by teammates is a great example).

I believe the crux of your argument is "I can't think of how to do this well, so it must not be compelling." That seems like a very weak foundation for an argument. While I will concede that there are roomless systems that are more complicated, I think that's about as useful as saying that a $90 graphing calculator is more complicated than a cheap $5 calculator: They are used for different things, and attract their respective audiences :)

I second Kelvin's response.

Line of sight is not a room. Rooms are rooms. Line of sight can work exactly the same way in a completely roomless world as it can in a world implemented in rooms. It can ever work better in worlds implementing rooms:

In LP-based MUDs, you could be sitting on the street and LOOK THROUGH WINDOW AT BOOK ON TABLE. You could pull out a bow-and-arrow and SHOOT someone three 'rooms' down the street.

I think the argument is entirely baseless, because you either have rooms divided INTO areas, or areas that are single rooms.

I grant you that on paper, the all-pairs-shortest-path algorithm is nasty, O(n^3) I think? But in practice I can't see where it would take more time to compute LOS on (likely) a half-dozen paths within that radius of 6 rooms, than to touch all the rooms in question. Let me make an observation here… while true path-finding requires you to paw through a much larger space because a path can be convoluted, line-of-sight does NOT have the same requirement. If your distance is 6 rooms, any path longer than 6 rooms doesn't have LOS because you can't see around corners (without help). Even if you want to put some slop in to handle edge cases where the angle would make the path 9 rooms (and you shouldn't… that implies too fine a granularity on your room size, and means maybe rooms aren't a good idea), that's still far less than walking the whole map.

I'm not a math guy, so if I'm wrong, so be it. If you're bored though, you might want to try that as an alternative algorithm just for amusement. I'd try it on my old Diku, except I'd have to implement propogation, and knowing DikuMUD, I'd be debugging pointer errors for the rest of the week. *chuckle*

Hah those pictures of souped up cars was awesome :P

@Tyche, Idealiad: The main reason is because it's a good fit for the world I'm building. I'm designing a sky scraper with mostly closed spaces, corridors, etc.. So I think the room concept applies really naturally. Also, though the rooms themselves have coordinates, I'm not tied to a particular grid. This allows me to design areas that would be very hard if I had used a grid (which is typically a necessity in a roomless environment, I think). For example, the floors of the skyscraper are actually round, each floor being a larger circle than the one below. It's inspired by the following skyscraper: http://www.evolo.us/competition/airport-... This would be really hard to create on a grid.

Also, I would like the MUD to be purely text-based. No additional GUI parts, or ascii art necessary. While the tile grid in Frontier looks very innovative, it's not what I'm trying to build :)


@quixadhal: It's a good point about line of sight simplifying the pathfinding, but it doesn't apply to sound of course :)

A room-based system isn't defined by having locations that represent literal rooms. It's simply a way of breaking up the environment (for the purposes of movement, combat, communication, etc) into abstract encapsulated nodes.


I've seen the same in some DikuMUDs. It's a good example of someone working around the limitations of a room-based system; in a roomless mud, you get behaviour like the above for free.


You also said you want "someone throwing a granade … The corridor is tight and the pressure of the explosion is compressed into two directions … The sound of the blast will alarm everyone within hundreds of yards". That sort of behaviour is easier to handle in a roomless mud, because you don't have artificial boundries for the grenade, explosion and sound to cross over.

A roomless model can also handle enclosed spaces perfectly well - see here for example, or have a look at some roguelikes, or Dwarf Fortress, etc.

Yeah it is pretty easy to do, with portals.