Original post from Grim123, taken from the ezboard forum
Hey Guys,
Long time no see

I know I haven't posted here in ages - years in fact, But I figured someone here would probably be better equipped to help me with my latest problem than over at Coders Workshop.
Anywayz, As you may or may not know, I have been working on a raycast engine which is basically like Doom. What I am having a problem with is as follows -- This is cut-and pasted from the topic I started over at Coder's Workshop(Btw a sector is just a polygon for this discussion):
You know how with a Doom map editor you create the map sector by sector right? And basically, You draw these sectors, And then you can click somewhere inside the sector you just made and use the 'create sector' option -- And the map editor somehow detects which lines are making up that sector right?
Well, That is what I'm trying to figure out. How to make an algorithm where the person who is creating the map can just draw the map how they like, And then click within a closed set of lines, And have the map-editor automatically detect which lines make up that sector/polygon. I know I can do it manually, But this would make it tedious for making maps, I would much rather take the extra step to get the map-editor to do it automatically. Trouble is -- How do you get it to detect which lines make up 1 sector when ALL of the lines of the map are connected?
If anyone has any ideas, I'd love to hear them! Or if you could point me to some information you might know of that exists on the net. If I can implement this technique, It will make the map-editor much easier to use, And save a lot of time.
My map editor is already capable of making maps, With Zoom in/Out capability etc, I just want it to autodetect sectors when I click inside a completed one. Basically, All the routine needs to do is to define which lines belong to each sector/polygon... I can define them manually, But that defeats the purpose of 'ease of use' - Cause the rest of the map editor is pretty easy to use so far. I hope this makes more sense!
Anyway, With the old dos map editor for Doom called Waded, You don't have to create the sector right after drawing it. The program will allow you to draw a whole map first if you want -- And then later click inside an area that you want to make a sector, And Somehow, The map editor can distinguish which particular lines make up that closed sector.
So...I'm stumped. Anyone have any ideas on how to accomplish this? I just want ideas/algo's, Not actual code, Because I want to do my own programming.
Thanks in advance!

And it feels good to be back here

5H0CKW4VE
*Administrator*
Posts: 7947
(4/10/05 14:32)
Reply | Edit | Del
ezSupporter
New Post Re: Need some help with an algorithm please

Got to have a think about this, nice to see you back Grim

¤´¨)
¸.·´¸.·*´¨) ¸.·*¨)
(¸.·´ (¸.·`¤... SHOCKWAVE / DBF...¤
VISIT DARK BIT FACTORY INTERACTIVE! (please!)
Grim123
ZX SPECTRUM
Posts: 50
(4/10/05 23:08)
Reply | Edit | Del New Post Re: Need some help with an algorithm please

Thanks Shockwave -- Good to see you too

This one is a toughie, heh. I've been thinking about it some more, And the only solution I could come up with is using raycasting within the map editor to determine the linedefs making up a sector. However, This would require the sectors to all be convex -- Which I can see causing lots of problems. I dunno... But there has to be a way to do this, Well, I know there is because 'Waded' does it. Sorry, I always seem to ask the hard questions lol!

If all else fails, I will just have to make it so the user manually clicks on each line in succession that they want added to a sector. That will be a last resort though.
-Grim-
zawran
Zawran / TTD
Posts: 2092
(4/10/05 23:10)
Reply | Edit | Del
New Post Re: Need some help with an algorithm please

I am having a bit of a problem visualizing it. Can sectors be of any shape? Like a L-shape, a U-shape, or are they all made up of maximum 4 points / 4 walls?
http://zac-interactive.dkGrim123
VECTREX
Posts: 51
(5/10/05 0:09)
Reply | Edit | Del New Post Re: Need some help with an algorithm please

Hey Zawran,
Yes, Sectors can be any shape - Well, That is convex or concave at least, And use any number of points, That is why I am having so much difficulty in figuring out a solution :/
Basically, Picture it like this: The user making the map draws out their entire map line by line. Then, After the map is drawn, They start creating sectors by clicking inside each area of the map that forms a closed polygon. The map editor should be able to automatically add the correct lines that belong to that polygon. Does this make more sense?
-Grim-
Grim123
VECTREX
Posts: 53
(5/10/05 4:18)
Reply | Edit | Del New Post Re: Need some help with an algorithm please

Hey guys,
If it would help, I can also send you a copy of the 'Waded' map-editor for Doom. Although, You will need one of Doom's Iwad's (Doom.wad or Doom2.wad) to run it.
-Grim-
zawran
Zawran / TTD
Posts: 2101
(7/10/05 15:46)
Reply | Edit | Del
New Post Re: Need some help with an algorithm please

I am not really sure how to go about this one. I remember trying something similar way back when I was working on a doom clone with B3D and wanting to keep the editor 2D with just lines. But I didn't find any solutions on it back then and had to stick with manually making the room connections.
http://zac-interactive.dkGrim123
VECTREX
Posts: 62
(7/10/05 23:21)
Reply | Edit | Del New Post No big deal

That's allright man,
I've been trying to figure this one out, And nothing seems to be the right answer, So I'm probably going to just make it so that the person making the map has to manually create sectors by clicking on each linedef seperately -- Unless Shockwave pops in here with a brilliant idea to save the day,lol

Or someone else.
Thanks anywayz guys!

-Grim-
jimshawx
ZX SPECTRUM
Posts: 35
(8/10/05 5:25)
Reply | Edit | Del New Post subject When you define the level, it just looks like a maze? Are there doors separating the sectors? How do you decide manually what a sector is? Is there a mathematical definition, or is it just a look-and-feel thing for a user to do it?
Any algorithm you might pick would probably start with any random unused line (wall), and then recursively add walls until it links back up again. If it doesn't link up again down one branch, you have to recurse down another branch until it does. At any time where more than 2 lines meet, you might want to use a heuristic to, say, always go round in a clockwise direction first. That's more likely to bring you back to where you started. Use a cross product to find out the direction of the new line with respect to the last two.
Once you have a circuit, remove it from the map and start again.
Obviously, depending on how the maps are drawn there might be gaps or L shapes or doors that need to be used twice or only one circuit, etc, etc. You could try fixing that by adding dummy walls to the map before you start looking for circuits/sectors/areas whatever you call them.
That's how I'd approach it anyway.
Jim
Grim123
VECTREX
Posts: 63
(8/10/05 7:06)
Reply | Edit | Del New Post

Well,
In this case, The sectors are just like Doom's -- Any set of lines that form a polygon which is either convex or concave - Without overlapping lines.When I say manually adding the lines to a sector, I mean that after the user draws out the map, They would then go into sector mode by pressing a button, And then click on the lines they wish to define a sector. If they do it incorrectly, The engine will crash - Simple as that. But sectors are not difficult at all to draw - It's just a fancy name for a 2d polygon really. I thought about the clockwise thing -- But there are a lot of times that you would end up with a sector that doesn't have all of the lines going in a clockwise motion -- such as a concave sector. Anywayz, I guess I can try to tackle this problem later, Manually creating the sectors is just more tedious, But it will work just fine too. I don't know how 'Waded' does it, But they're map editor does the automatic technique very well.
-Grim-
jimshawx
ZX SPECTRUM
Posts: 36
(9/10/05 0:07)
Reply | Edit | Del New Post crash?
Quote:If they do it incorrectly, The engine will crash - Simple as that
If both convex and concave polygons are allowed, how can a sector be incorrect? Is it just if the polygon is incomplete or has lines that cross?
Quote:I thought about the clockwise thing -- But there are a lot of times that you would end up with a sector that doesn't have all of the lines going in a clockwise motion -- such as a concave sector
That's what a heuristic is. A rule that isn't hard-and-fast, it's just true sometimes and gives you a better result than blind random choice. For instance, in the classic Travelling Salesman problem, a heuristic choice might be preferentially to visit a town you haven't been to before instead of going back somewhere you've already been. But that doesn't always help since some towns are up dead ends.
Clearly if you want your algorithm to join up the sectors more rapidly then the higher the ratio of right turns over left turns, the better.
Travelling Salesman if often solved by an algorithm called Djikstra's Algorithm. You'd be wanting to use something very similar to that to work our your sectors automatically. Another name for it is the A* algorithm.
I haven't seen Waded, but I take it the kind of sectors you're talking about are the ones that appear when you go from one area to another on the ingame maps in Doom?
If so, it's the doors that are the key to working out where the sectors are, because they are the boundary between one sector and another.
Jim
Grim123
VECTREX
Posts: 64
(13/10/05 8:34)
Reply | Edit | Del New Post Re: Quote:
--------------------------------------------------------------------------------
If both convex and concave polygons are allowed, how can a sector be incorrect? Is it just if the polygon is incomplete or has lines that cross?
--------------------------------------------------------------------------------
Yes, Either incomplete, Or crossing lines.
Quote:
--------------------------------------------------------------------------------
That's what a heuristic is. A rule that isn't hard-and-fast, it's just true sometimes and gives you a better result than blind random choice. For instance, in the classic Travelling Salesman problem, a heuristic choice might be preferentially to visit a town you haven't been to before instead of going back somewhere you've already been. But that doesn't always help since some towns are up dead ends.
Clearly if you want your algorithm to join up the sectors more rapidly then the higher the ratio of right turns over left turns, the better.
Travelling Salesman if often solved by an algorithm called Djikstra's Algorithm. You'd be wanting to use something very similar to that to work our your sectors automatically. Another name for it is the A* algorithm.
--------------------------------------------------------------------------------
Yes, I know about the A* algorithm, And I also know what a heuristic is. I don't want an algorithm that is only right part of the time though, Or, Basically making guesses -- It should be able to make a sector correctly every time, Providing the person drawing the polygon abides by the rules stated above.
Quote:
--------------------------------------------------------------------------------
I haven't seen Waded, but I take it the kind of sectors you're talking about are the ones that appear when you go from one area to another on the ingame maps in Doom?
If so, it's the doors that are the key to working out where the sectors are, because they are the boundary between one sector and another.
--------------------------------------------------------------------------------
Yes, Just like the ones in Doom -- I take it you haven't used a Doom map editor before then? Because, Doors are not what makes the boundary between one sector and another, It's a two-sided Linedef that decides the boundary -- There are several sectors that are connected in many maps that don't use a door to seperate them. A door in Doom is simply a sector which moves up and down, You can make any sector in Doom into a door. Anywayz, Never mind -- I appreciate the suggestions, But it's clear that we aren't quite on the same page. The heuristic was a good suggestion, But I need something that will work all the time - without fail, Not just sometimes.
So, I am just going to make the sectors a manual operation until I figure it out for myself.
-Grim-
Grim123
VECTREX
Posts: 67
(14/10/05 7:52)
Reply | Edit | Del New Post Found a solution!!

:grnpep :grnpep :grnpep
Hey guys, I have good news!
I just saved a ton of money on my car insurance by switching to Geiko. Just kidding, Lol

I came up with another way of automatically creating sectors which I have now implemented in the map editor. There is a small amount of manual operation required, But it is very easy to create a sector now, And they are created the same time that the walls/Linedefs are drawn. Anywayz, This is what I came up with: I have 2 fields in the type for the
Linedef(wall type) that store the sector that the linedef belongs to. Why 2? Because in situations where 2 sectors share one Linedef. Anywayz, It works as follows:
1> the person drawing the map presses the 'N' key to start a new sector.
2> They then begin placing lines, The lines are red until placed, They then become green after the second vertex of the linedef is placed -- Denoting that this line is now a part of the current new sector.
3> after drawing a sector, The person then hits the 'N' key again to start a new sector. The sector that was just finished turns blue to show that it is finished. So all sectors that are completed will be blue lines -- This makes it easy to tell which lines are being added to the current sector.
4> during the drawing of the linedefs, The vertex's of the current line being placed are compared to all of the previous lines already placed, And if the start and end vertex's match to the start and end vertex's of any line previously placed, The map-editor knows that this is a line that is shared between 2 sectors, And doesn't create a new line, So no lines overlap. The line that is shared then turns green to show that it is a part of the new sector. You will have to draw a line over the top of an existing line if it's needed to close off a sector, But it doesn't make a line when you do this, Just turns the line underneath into a 2 sided linedef basically
I will also have a feature where you can cycle between the different sectors, So that you can visually make sure they are all correct. But, So far, The editor works flawlessly It is really pretty easy using this method. All the person making the map editor has to do is make sure to press 'N' to create a new sector, And then create a closed polygon shape out of linedefs for a new sector.
Well, I appreciate everyone's help!!
:nanasplit
-Grim-
zawran
Zawran / TTD
Posts: 2108
(14/10/05 9:51)
Reply | Edit | Del
New Post Re: Found a solution!!

That sounds like a very good solution to me. I might even use that idea if I one day return to making a 3d game.
http://zac-interactive.dkGrim123
VECTREX
Posts: 70
(14/10/05 22:34)
Reply | Edit | Del New Post Re: Thanks, And feel free to use it!

-Grim-