Maze generator and map rotator
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
Maze generator and map rotator
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.
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 145 times
-
- maprotator.tar.gz
- Added my own copyright header
- (1.91 KiB) Downloaded 142 times
Last edited by Lucifer on Tue Nov 01, 2005 9:39 am, edited 1 time in total.
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,..
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,..
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
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?)
You can see how the grid datastructure looks like by pressing "d" on a client compiled with DEBUGLEVEL>=3. (Did I say that already?)
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
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 haveLucifer wrote:Is it possible to compare two line segments at different locations and determine which is greater/lesser the other?
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.
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
- Tank Program
- Forum & Project Admin, PhD
- Posts: 6711
- Joined: Thu Dec 18, 2003 7:03 pm
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
- Tank Program
- Forum & Project Admin, PhD
- Posts: 6711
- Joined: Thu Dec 18, 2003 7:03 pm
The most simple formula would be
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.
Code: Select all
x=a cos(phi)
y= b sin(phi)
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
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.
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.