Auto-generating maps

For developmental things relating to the graphics of the game.
User avatar
philippeqc
Long Poster - Project Developer - Sage
Posts: 1526
Joined: Mon Jul 12, 2004 8:55 am
Location: Stockholm
Contact:

Post by philippeqc »

nemostultae wrote:I am working on a maze generator in Ruby. I came across this, and it is very helpful.

Here are a few examples in C, and some more general docs.
*cough* randomly generated maze *cough*

*cough* properly distributed zones *cough*

-ph
Just clearing my throath ;)
Canis meus id comedit.
User avatar
Lucifer
Project Developer
Posts: 8640
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

What would it do to fps to generate the map as a series of wall segments of only two points each? I'm curious, I googled up a python maze generator that I wouldn't mind beating on a bit to include spawn points and zones, but it would be a fair rewrite to make it draw longer walls. Maybe.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

Well, at the points where two walls meet at a corner, there will have to be a point anyway. The only case where there will be an unneeded additional point is when only two wall segments meet that could have been joined to one continuous segment; probability estimate of that is one in eight corners. That's negligible. The engine adds unneeded extra points all on its own to a much greater extent.
User avatar
Lucifer
Project Developer
Posts: 8640
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Ok, so the generated mazes have tons of points that are in a line on a wall. Here's some talk about the maze generator so the rest will make more sense. :)

The maze generator generates grid mazes. It builds a list of lists, rows and columns. In each item in the column (which is inside the row) it stores whether or not there is a wall on the bottom and whether or not there is a wall on the right. That part doesn't matter. What matters is that I converted it to build arma maps by multiplying the indexes of the arrays while iterating through them by some factor, and then setting a grid size that made len(rowItem) * sizeFactor = 500. So it's a 500x500 grid.

The factor currently used is 20, and it generates 25x25 grid. I'd like (and so would some others) to generate a 50x50 grid by changing the factor to 10. Obviously that's a pretty large grid. As a result of this scaling, there is a point at every single interval. So 0,0 has a point, 0,20; 0,40; 0,60; and so forth. Then 20,0; 20,20. And so forth. And then there are long hallways going this way and that way and the other, also short hallways. It's pretty neat. But there are definitely a lot of points that are being generated that aren't being used.

I went, in local game, from 250fps down to 7fps with the 50x50 grid. On the other hand, I only dropped to about 100fps on the 25x25 grid. On internet game, I've only put a 25x25 grid on the server, nothing larger, because of that dramatic drop in fps. It'd be nice if we didn't have such a huge drop in fps anyway.

Tzeentch, the first labyrinthine map I'm aware of (and that's arguable) runs at around 60fps for me. But it's a spiral, mostly, rather than a real maze.

So my question comes back, how much does it affect fps? More to the point, how much is it adversely affecting fps that could be recovered in such a volume to justify putting a priority on removing redundant points and joining wall segments, at least when they're in a straight line?
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
User avatar
philippeqc
Long Poster - Project Developer - Sage
Posts: 1526
Joined: Mon Jul 12, 2004 8:55 am
Location: Stockholm
Contact:

Post by philippeqc »

Lucifer:
Ok, its a long and boring process, but you could "hand-optimise" a 25x25 maze, and compare the fps to the same map with points at every grid intersection.

(Idea to help you hand optimise: Set some absurbly high wall height on all the walls from the start. As you optimise a wall, mergin its sub segments, change its heigh to something low, like "2.0". A quick run in the game will show you if you forgot to merge some walls together.)

I'm sorry I dont have more insigth into the performance of the engine.

Good luck, I sure hope you find some good performance in there, I'm still in software rendering here ;)

-ph
Canis meus id comedit.
User avatar
Lucifer
Project Developer
Posts: 8640
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

I've been thinking it over, and in the time it would take to hand-optimize, I think I could write an algorithm to do it automatically.

I'm also thinking of ways to make the mazes more balanced. I don't know if anyone's noticed, but some spawn points really are closer to the center than others. It's that depth-first generation, it generates a maze that starts in the lower-left corner and terminates at the upper-right corner, but I threw it all out of whack by putting the terminus in the center and setting up 8 start points around the outside.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

Lucifer wrote:So my question comes back, how much does it affect fps? More to the point, how much is it adversely affecting fps that could be recovered in such a volume to justify putting a priority on removing redundant points and joining wall segments, at least when they're in a straight line?
You can't expect more than a 10% gain from optimizing the map. If you run a client in debug mode (DEBUGLEVEL>=3) and press "d", you'll see all the additional points the engine puts in. They're legion and will still be there after your optimization. The engine is just not good for complicated situations at the current stage.
User avatar
joda.bot
Match Winner
Posts: 421
Joined: Sun Jun 20, 2004 11:00 am
Location: Germany
Contact:

Post by joda.bot »

Is anyone actually working / thinking about some means to add atleast frustum culling ? (to speed up lucifers mazes)
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

I think that is a subtopic of the planned rendering refactoring/potential engine switch. All by itself, without a spatial hierarchy, frustum culling is quite useless as the GPU already does it on a per-polygon basis (and our walls are just single polygons), so just adding it now would benefit nobody.
Post Reply