whats a good number to test map generation?

[magellan]

I finally got something like a dungeon map generator to work, but i dont really trust it.

So i just ordered it to make 1000 maps, and it did, which made me a little more confident, but i wonder if 1000 is good enough.

So i wonder if i should ask the devs here what they consider a good number to test the reliability of a map generator.
Oh, i guess i just did

[Slash]

To ensure the quality of the programs, I almost always test my dungeon map generators with 776 maps.

[magellan]

If you are messing with me: Ok, got it yeah... guess it isnt the smartest question ever

If you are not I must ask: Anything special about that number that I am not getting?

[ido]

You just wait till you get bitten in the ass by map number 777!

We'll see who's laughing then...

[Ex]

I've found that whatever is the worst case scenario for dungeon generation tends to be among the more common scenarios. Granted, it took me hundreds upon hundreds of dungeons to notice a fairly major flaw in Dreamhack's dungeon generation. But in general, I've found for me that if something can go wrong, it will very quickly and easily.

I'd say 1000 dungeons is way more than enough to verify the integrity of a dungeon generator. But there's always the chance...

[Krice]

So i wonder if i should ask the devs here what they consider a good number to test the reliability of a map generator.

I think all you need to do is make sure the player doesn't get stuck in the map. You can do that by giving possibility to dig through walls (to solve dead end bugs) and make sure that exits are created no matter what.

[Darren Grey]

Or better yet use a floodfill procedure to ensure that the map is fully connected.

[corremn]

Yep flood fill is great. And really easy to. Every one should use it. It could easily be modified to run over multiple levels, or your entire dungeon complex to see if there are non-connected regions. 

What you need to do is create a test algorithm and then run any number of generations. I generally only use floodfill and a check-every-square routine to see if it has appropriate neighbours.  E.g a door in the middle of nowhere or on a corner, etc.

Of course you need a set of things to test for.  Playing the game will back up the tests. I have a quick gods view button (I assume most devs do) that can quickly show me the entire map when I am debugging or when things seem a little strange.

[Darren Grey]

I suppose a dungeon needs certain basic things:

1. All areas connected.
2. All edge squares are impassable/walls.
3. "Looks nice" (a little hard to define, but basically the map comes out the style you're after).
4. Loops in the dungeon (important for gameplay).

I'd say 100 tests would be good enough for the more qualitative 3 and 4, but you want 1 and 2 to be really hardcoded to never fail.  In some games other stuff like ensuring chokepoints and min distance between stairs might be important too.

[rdc]

This is actually a general case problem in programming. There is really no way to say definitively that an algorithm will be correct 100% of the time, due to the nature of the problem. (Here is part of an article I wrote on the subject which sites some examples: http://virtualink.wikidot.com/mcplx2).

There are some ways to approach the problem though. A program will usually malfunction at the limits of the algorithm being employed. For example, you built this nice string parsing function: what happens when you pass it an empty string? Or a string with no spaces? Or a string with no recognized tokens?

In the case of an RL, you can test limit conditions by doing crazy things. What happens when you try to make a 1000 rooms? Or one room? Or no rooms? If the program handles the limit conditions without a major crash, then you can feel fairly confident that in the normal case, the program will probably work ok.

[Krice]

There is really no way to say definitively that an algorithm will be correct 100% of the time, due to the nature of the problem.

This doesn't sound right. I believe simple algorithms with well defined limits always work, because that's their nature. But sometimes the dungeon generation is too complex and layered for everything to work in all possible situations. Even then there are ways to prevent the generation of totally unplayable levels.

In cases where you don't know exactly how the dungeon generation is going to work it's really useless to test it, because you might be able to run 1000 tests without problems, but it's still possible to produce errors randomly in rare cases.

[rdc]

This doesn't sound right. I believe simple algorithms with well defined limits always work, because that's their nature. But sometimes the dungeon generation is too complex and layered for everything to work in all possible situations. Even then there are ways to prevent the generation of totally unplayable levels.

This is of course assuming you know exactly what is going on in the compiler and the compiler itself is guaranteed to be absolutely bug free, that all the supporting libraries are bug free, that the OS doesn't have any bugs in it ...

A simple Hello World program in reality is not so simple and is dependent upon a large chain of events that have started long before you wrote a single line of code. Many people seem to forget that compilers, libraries, OSes are programs too, and are subject to the same problems as any program. A problem in any part of the chain that ends in your simple Hello World program can affect this simple algorithm.

This is why you can never say with absolute certainty that any algorithm, even a Hello World, will operate correctly in every case.

[PaulBlay]

Basically, see Gödel's incompleteness theorems. 

[Krice]

This is why you can never say with absolute certainty that any algorithm, even a Hello World, will operate correctly in every case.

I thought we were talking about theory here, restricted to the dungeon generation. It's not a fault of the dungeon generation routine if a library routine or the computer itself fails to work properly.