Progress thread for original version (2006)
Moderator: benryves
yeah, the sky looks fine as it is. Don't sacrafice performance to make it a little better. This is a calculator, not a powerful gaming rig that can play games with all the graphics options turned on. Concentrate on making something that looks decent and runs fast. It won't be very fun to play if it looks amazing but runs at like 3 seconds per frame. You do have a great engine though, and you are great at programming. Maybe you can find a way to have more eye candy along with good speed. But speed is important, more so than eye-candy. ![Smile :)](./images/smilies/grayscale_smile.gif)
![Smile :)](./images/smilies/grayscale_smile.gif)
In Memory of the Maxcoderz Trophy ![Image](http://img88.imageshack.us/img88/9374/4x5yrtrophytg1.gif)
![Image](http://img88.imageshack.us/img88/9374/4x5yrtrophytg1.gif)
- thegamefreak0134
- Extreme Poster
- Posts: 455
- Joined: Mon 23 Jan, 2006 10:09 pm
- Location: In front of a Computer, coding
- Contact:
-
- Calc Master
- Posts: 1089
- Joined: Fri 17 Dec, 2004 9:53 am
- benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
The greyscale effect is optional (adds about 8 lines of code, only runs once per frame and can be disabled with a single switch in the engine package's Settings.inc file.
![Image](http://benryves.com/images/nostromo/gs_optional.gif)
Anyway, I've started throwing together a very primitive level editor. (GDI+)
![Image](http://benryves.com/images/nostromo/level_editor.gif)
Insert inserts a new vertex at the mouse location; delete removes the closest vertex. Point at a vertex, hold W, move to another vertex and release W to insert a new wall. (Single-sided, hold shift at the same time to add a double-sided wall). Use D to remove walls in the same way. That sort of thing.
The two different types of wall are represented with white lines (single-sided) and grey lines (double-sided). There are therefore 9 different sectors in the above image.
Imagine that the walls have been kept simple (fixed floor/ceiling heights, single segment) and can have one of 6 different 'colours' - from 0 (invisible/transparent) to 1 (white) through to 3 (50% grey) and finally 5 (black).
Therefore, for the sake of simplicity, assume that all of the double-sided grey walls in the above screenshot are invisible. The room in the south-west of the screenshot is an octogonal room with a doorway in the eastern wall and a square pillar in the middle.
The four double-sided walls in this south-western room are not redundant. You will notice that the level has been cut up into convex sectors. This has one small advantage - it reduces the number of walls that will need to be sorted, as I only need to sort entire sectors for occlusion purposes.
Also, I can see that I can get some sort of portal*-based system up and running. Suppose I use the editor to create this:
![Image](http://benryves.com/images/nostromo/level_editor_door.gif)
If I was to start in the left sector, I would go through and draw each wall. I'd hit the double-sided wall at some point, and know that after this sector I'd have to move into the sector in the middle. After that sector, I'd know that I'd have to move to the sector to the right. With me so far?
Let's do something radical and make that central sector a door, and close it (move the ceiling height down to meet the floor height). This time, when I move through the sectors, I'll hit this sector and see that it's closed. No matter, say I - rather than carry on walking through the sectors, I stop at that point.
By liberally sprinkling a world with doors, and keeping them shut most of the time, you can cut out a fair chunk of geometry.![Smile :)](./images/smilies/grayscale_smile.gif)
I cannot think of the best way to handle sorting. I don't think I can just use the order in which I wander through the sectors - imagine this:
![Image](http://benryves.com/images/nostromo/sorting_by_sector_bad.gif)
Imagine you're in the north 'triangle' and looking south. As you can see, you need to travel through more sectors to get to the larger rectangular room than the south triangular room - and using that for sorting is just wrong.
One potential workaround I can think of is that each sector has a visibility list - a list of in which order sectors appear (in front->back order - else we wouldn't be able to take advantage of portals). Problems; MASSIVE amount of data that grows exponentially with each added sector! From what I can also tell, that also seems a precomputed BSP list, done per sector (rather than work out which side of the split to follow each branch, it's already calculated for us). On the other side, this can also be used to calculate (through some nifty ray/plane intersection algorithm) which sectors will NEVER be visible from a particular sector... Hmm. I'm not afraid of 'wasting' RAM with gigantic tables - if we assume a smallish, plain level of 50 sectors, each sector would need a list of at most 49 other sectors. 49*50*2=4900B - not actually too bad. :\
(Bah) Just realised that would not work (precomputed sorting based on sectors) at all.
![Image](http://benryves.com/images/nostromo/bah_sorting.gif)
Let's say the red line is your 'view' (not a wall, quick and dirty diagram). It intersects the front of two walls, so it appears that the sort should go north->east->west sectors. However, imagine I move to the other side of the sector and look the same way (mirror the diagram, basically). Now the order goes north->west->east, and I'm still in the same sector
Do I just clump all the sectors together and sort them all together based on the distance to the central (average) coordinate of each and the camera? (Not fast!)
It's still not entirely a bad thing, as the list could still be used to roughly sort the sectors (some sorting algorithms work well on nearly-already sorted data, even bubble sort). Even then, the information of which sectors are visible/entirely invisible could still be used.
Thoughts?
---
*I hope that's the correct word.
![Image](http://benryves.com/images/nostromo/gs_optional.gif)
Anyway, I've started throwing together a very primitive level editor. (GDI+)
![Image](http://benryves.com/images/nostromo/level_editor.gif)
Insert inserts a new vertex at the mouse location; delete removes the closest vertex. Point at a vertex, hold W, move to another vertex and release W to insert a new wall. (Single-sided, hold shift at the same time to add a double-sided wall). Use D to remove walls in the same way. That sort of thing.
The two different types of wall are represented with white lines (single-sided) and grey lines (double-sided). There are therefore 9 different sectors in the above image.
Imagine that the walls have been kept simple (fixed floor/ceiling heights, single segment) and can have one of 6 different 'colours' - from 0 (invisible/transparent) to 1 (white) through to 3 (50% grey) and finally 5 (black).
Therefore, for the sake of simplicity, assume that all of the double-sided grey walls in the above screenshot are invisible. The room in the south-west of the screenshot is an octogonal room with a doorway in the eastern wall and a square pillar in the middle.
The four double-sided walls in this south-western room are not redundant. You will notice that the level has been cut up into convex sectors. This has one small advantage - it reduces the number of walls that will need to be sorted, as I only need to sort entire sectors for occlusion purposes.
Also, I can see that I can get some sort of portal*-based system up and running. Suppose I use the editor to create this:
![Image](http://benryves.com/images/nostromo/level_editor_door.gif)
If I was to start in the left sector, I would go through and draw each wall. I'd hit the double-sided wall at some point, and know that after this sector I'd have to move into the sector in the middle. After that sector, I'd know that I'd have to move to the sector to the right. With me so far?
Let's do something radical and make that central sector a door, and close it (move the ceiling height down to meet the floor height). This time, when I move through the sectors, I'll hit this sector and see that it's closed. No matter, say I - rather than carry on walking through the sectors, I stop at that point.
By liberally sprinkling a world with doors, and keeping them shut most of the time, you can cut out a fair chunk of geometry.
![Smile :)](./images/smilies/grayscale_smile.gif)
I cannot think of the best way to handle sorting. I don't think I can just use the order in which I wander through the sectors - imagine this:
![Image](http://benryves.com/images/nostromo/sorting_by_sector_bad.gif)
Imagine you're in the north 'triangle' and looking south. As you can see, you need to travel through more sectors to get to the larger rectangular room than the south triangular room - and using that for sorting is just wrong.
One potential workaround I can think of is that each sector has a visibility list - a list of in which order sectors appear (in front->back order - else we wouldn't be able to take advantage of portals). Problems; MASSIVE amount of data that grows exponentially with each added sector! From what I can also tell, that also seems a precomputed BSP list, done per sector (rather than work out which side of the split to follow each branch, it's already calculated for us). On the other side, this can also be used to calculate (through some nifty ray/plane intersection algorithm) which sectors will NEVER be visible from a particular sector... Hmm. I'm not afraid of 'wasting' RAM with gigantic tables - if we assume a smallish, plain level of 50 sectors, each sector would need a list of at most 49 other sectors. 49*50*2=4900B - not actually too bad. :\
(Bah) Just realised that would not work (precomputed sorting based on sectors) at all.
![Image](http://benryves.com/images/nostromo/bah_sorting.gif)
Let's say the red line is your 'view' (not a wall, quick and dirty diagram). It intersects the front of two walls, so it appears that the sort should go north->east->west sectors. However, imagine I move to the other side of the sector and look the same way (mirror the diagram, basically). Now the order goes north->west->east, and I'm still in the same sector
![Sad :(](./images/smilies/grayscale_sad.gif)
It's still not entirely a bad thing, as the list could still be used to roughly sort the sectors (some sorting algorithms work well on nearly-already sorted data, even bubble sort). Even then, the information of which sectors are visible/entirely invisible could still be used.
Thoughts?
---
*I hope that's the correct word.
I dunno what restrictions the editor puts on sectors, but a centroid sort will not handle all possible cases:
The left sector is closer than the right according to the centroids. It feels a little stupid to pose sector restrictions on mappers and having more vertices/walls isn't very efficient I guess.
Gosh I'm glad I never got this far with z80
I'll give the problem a thought though.
EDIT: What about sorting by centroid of the portal/double-wall? I've forgot about a lot about sorting, but bubble sort shouldn't be too bad with the few sectors that will be in play. Linear or shell sort maybe?
EDIT 2: There's a problem with portal-sorting if you allow shallow angles inside the sectors, if you go with the prism-brush idea, it'd probably work (I don't know enough topology-maths to proove it
).
Code: Select all
_____________
| |
| *| <- Camera
|...._.....___|
| | | |
| x | | |
|___| | |
| |
| x |
| |
| |
| |
|___|
Gosh I'm glad I never got this far with z80
![Very Happy :D](./images/smilies/grayscale_happy.gif)
EDIT: What about sorting by centroid of the portal/double-wall? I've forgot about a lot about sorting, but bubble sort shouldn't be too bad with the few sectors that will be in play. Linear or shell sort maybe?
EDIT 2: There's a problem with portal-sorting if you allow shallow angles inside the sectors, if you go with the prism-brush idea, it'd probably work (I don't know enough topology-maths to proove it
![Razz :P](./images/smilies/grayscale_grin.gif)
- benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Aha, true. The only 'restriction' is that sectors are convex.coelurus wrote:I dunno what restrictions the editor puts on sectors, but a centroid sort will not handle all possible cases
Lucky youGosh I'm glad I never got this far with z80I'll give the problem a thought though.
![Wink ;)](./images/smilies/grayscale_wink.gif)
I'm still not too hot on understanding the prism-brush idea :\EDIT 2: There's a problem with portal-sorting if you allow shallow angles inside the sectors, if you go with the prism-brush idea, it'd probably work (I don't know enough topology-maths to proove it).
At the end of the day, I'll probably have to sort all visible walls anyway - to put sprites in the right place. Just a case of keeping things efficient.