Maze generator and map rotator

What do you want to see in Armagetron soon? Any new feature ideas? Let's ponder these ground breaking ideas...
User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Maze generator and map rotator

Post by Lucifer »

I'm a little too sleepy to wrap my head around the wiki's upload mechnisms to make it support python scripts and/or zip files, so here's the map generator and the map rotator.

Both of them are quick hacks, so don't expect to see wonderful code style or anything. The maze generator is based on someone else's code, I just added a method to generate xml maps for armagetron, but the core maze generation code is someone else's.

Both of these scripts are run from a cronjob, so they're built around being quick one-off runs instead of programs that run all the time. I'd like to change them or write another program that just tails the logs and then runs these scripts conditionally based on messages in the logs from the server.

Edit: I just noticed the line in the maze generator that says "Copyright blahblah All rights reserved". I guess that means I can't distribute it until I rewrite the maze-making algorithm. What a pain.

Edit2: Done.
Attachments
mazer.tar.gz
Now it's all mine baby
(4.28 KiB) Downloaded 105 times
maprotator.tar.gz
Added my own copyright header
(1.91 KiB) Downloaded 105 times
Last edited by Lucifer on Tue Nov 01, 2005 9:39 am, edited 1 time in total.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
SuPeRTaRD
Round Winner
Posts: 300
Joined: Fri Nov 05, 2004 11:53 pm
Location: bedlam
Contact:

Post by SuPeRTaRD »

this is cool, fun to try to find the way to the center zone

i think you aught to try emailing the author of the code, & asking permission..

you might not even need to, since armagetron is not a commercial release,..

or point out to him you intend to use it in a game for no profit.. or whatever..

blah..

i copywrite stuff sometimes, just put the clause in releases,, so ppl dont make a profit off me,..

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

It's not a big deal, the copyright thing. I looked a little further, and there is an author's copyright in there, it was the copyright of the C code I was looking at, but the author of the python code didn't put a license either. (It's an algorithm translated from C) But the algorithm that generates the mazes, the core of thing is suboptimal anyway and needs to be rewritten, so I'm wanting to do that already. And the interface provided by the Maze class is also pretty sucky and I'm expanding that, so it's not that big of a deal.

Maybe in a few days I'll be able to put a GPL header on it and re-upload it. :)

I'm enjoying the mazes too, a *lot*. But there are a few problems with the mazes themselves. Have you noticed how some spawn points are closer to the center than others? They're all technically about the same straight-line distance from the zone, but some are closer in the actual path than others. So I'm thinking of ways to correct that. I've got a dead end counter right now which I'll use to have it remove a certain amount of dead ends (configurable, of course). I was also thinking of having it just remove random wall segments.

Anyway, I've been reading a lot on maze generation, and it's both a lot simpler and a lot cooler than I ever thought it would be. I didn't write the maze generation algorithm it uses, but I will write the one it will use. ;)
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Bump.

I rewrote the base algorithm in the maze generator and pretty much the whole thing. So now it's much better. No more ASCII or html output, though. Also, it's *not* the maze generator that runs Labyrinth anymore, because of the rewrite. The mazes are now quite a bit funkier, and every wall is drawn twice in the resulting xml. I'll work on that, maybe in a few days. For now, more studying.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Z-Man
God & Project Admin
Posts: 11399
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

About the extra points the engine adds: maybe it is possible to minimize their use by randomizing the order of the walls as they appear in the map. When the walls are all laid out in grid order, you get long triangles with sharp angles at the opposite grid corners first; later, those triangles can't be rearranged well by the current algorithm.

You can see how the grid datastructure looks like by pressing "d" on a client compiled with DEBUGLEVEL>=3. (Did I say that already?)

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Hmmm, that should be fairly trivial to implement. I've encountered a separate problem, though. :)

So I eliminated the duplicate walls. Those were caused by the fact that my internal data structures stored a copy of every shared wall in each cell. The maze is built by called ripWall() on a cell object, and ripWall() has to rip two walls, its own and the one in the cell next to it. The end result is that every wall is stored twice.

Then I had an epiphany on how to combine walls. Simple, really, but an interesting algebra problem. Is it possible to compare two line segments at different locations and determine which is greater/lesser the other?

So my problem now is that since I've come up with a solution to the "too many points" problem, I have to implement it, no matter how trivial an improvement it makes. :(
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Z-Man
God & Project Admin
Posts: 11399
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

Lucifer wrote:Is it possible to compare two line segments at different locations and determine which is greater/lesser the other?
You won't like that answer: Yes, that is possible. But there is no canonical comparison possible between line segments. The mathematically most sensible thing would be to compare the segments' length, but I suppose that won't have the effect you want it to have :)
If your goal is to take this comparison, sort your walls with it, and then have combinable line segments next to each other in the sorted list, the answer is no. Just consider four walls composing a square; each wall would need to be next to its two neighboring walls in the list, but that's not possible in a linear list.
Perhaps it would be a good idea to use the left-hand-algorithm to walk through the maze, and collect the passed walls for combination? There, you'd have combinable walls next to each other. Depending on your maze, you'll have to run the collection several times until you got all walls.

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Actually, my solution (which I haven't managed to write yet) is to collect all the vertical segments in one list and all the horizontal segments in another. Then sort each list. Then iterate through it combining segments until there are no more to combine.

This will get it so that there is only the number of points needed to generate the maze, but it doesn't make all possible wall combinations. I don't know that it's needed to make all possible wall combinations.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Tank Program
Forum & Project Admin, PhD
Posts: 6709
Joined: Thu Dec 18, 2003 7:03 pm

Post by Tank Program »

If your wall segments are in a grid, go through each row of the grid, then check for continuity of said wall across the grid, combine wall segments that way into big walls (copying into another grid would be best I think.) Then, repeat for columns.
Image

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Ok, I implemented my solution and got unexpected results. :) Good results, I might add.

On a regular 25x25 grid, I got close to double the fps from the old generator. That's not free, though. The new maze generator is unbiased in its path-making algorithm, where the old one was biased. I'm considering how to add bias. So anyway, while I got more fps, it also meant that some spawn points were substantially closer to the center than others, so there was no contest. You either chose the right directon to start or you didn't, and if you did, then until a new maze was generated you got a lot of free points. The match winner was then determined by who got the sweet spawn point. :(

Still, the maze generator got a lot more flexible in the bargain. It scales, so you can have, say, a 10 x 40 grid. It can also cull dead ends and squares with only one path (2 walls). So it also makes a good general-purpose map generator when all you want is an irregular placement of obstacles with a few corridors here and there.

We also discovered a new and interesting effect to use on maps. Set a wall to a height of like 0.00001. I had considered doing that to make mines, but it actually makes invisible walls. So you can have an invisible maze. :) I, of course, made it possible to configure all this stuff with commandline options. But before I upload a new version, I want to add the option to use bias in the path generator (basic bias, more advanced will come later) and I also want to make the zone configurable. I.e. if you don't want a zone, it should't generate one. That way it can be used as a general purpose map generator just by culling a lot of dead ends and one-path squares.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Ok, new question. If given a diameter, like for a circle, I can easily compute coordinates of a given number of points on the circle. So in a square maze, I can find spawn points easily like that.

Using the same input, and adding any arbitrary definition of diameter you like, how would I compute coordinates for a given number of points on an ellipse? The center point is the same, it's the center of the arena (computed, of course). I can interpret diameter however is needed, but I'd really prefer to keep it as a single value if possible. The edges of the ellipse should be the same distance from the sides as the circle in the corresponding square arena.
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Tank Program
Forum & Project Admin, PhD
Posts: 6709
Joined: Thu Dec 18, 2003 7:03 pm

Post by Tank Program »

Don't elipses have two focal points and the distance to any point along its circumfrence is the sum of the distance of the to foci?
Image

User avatar
Z-Man
God & Project Admin
Posts: 11399
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

The most simple formula would be

Code: Select all

x=a cos(phi)
y= b sin(phi)
where phi is your angle between 0 and 2 pi, randomly chosen or regular as you like. a and b are the two radii; you'll want a/b to be the same as the aspect ratio of your rectangular area, so you'll probably want a = with * d/2, b = height * d/2 with one "diameter" value d between 0 and 1. Note that this won't be fair or even distributed equally; you'll get more spawn points closer to the focal points.

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

I guess I need to add in an aspect ratio to the function. I was trying to make it generic enough to draw circles and ellipses of any kind at any place, not just for spawn points. I want to lay out fortress zones with this algorithm where #zones == #spawn points, which should result in the zones being placed on the same spot as the spawn points, and I wanted to lay out other wall-based objects. Stuff like dropping tall circular/elliptical columns as landmarks, obstacles, or what-have-you. And then ripping out portions of the walls to make them chambers. :) It would be pretty cool to have a tall circular wall with a short maze inside, and the radius of the circle is equal to half the diagonal in the maze.

I'm moving the maze generator to a more general map generator, so it'll generate mazes, but can also be used to generate maps that aren't specifically mazes. At the heart of it will probably always be the maze carving algorithm, and that's fine. If someone wants a map generator that doesn't use a maze carving algorithm in its heart they can write one. ;)
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

User avatar
Lucifer
Project Developer & Local Moonshiner
Posts: 8610
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Hmm. Here it is, with a 75x75 maze grid. I noticed that when you stretch one of the axis (say, 50x75 grid) the spawn points still lie in a circle. :) It's a neat effect, and it's exactly what I was after. Now I just need to get the spawn points pointed properly, and then I can add real zone support.

But I noticed that the zone is off-centered here. I'm wondering if that's a bug in the maze generator or a bug in the previewer. I should go post a link to this from the previewer thread so nemo can see it.
Attachments
testmap-0.1.png
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden

Post Reply