That painter thing..
I'm struggling to think of a non clunky way of detecting when a 'box' has been surrounded and can be highlighted, like in the pic:
From the splendid Gamex
The best way I can think of is that a box gets coloured when a counter is zero, and the surrounding blocks decrease a particular counter (or counters for shared boxes). While this is simple enough it'll be a bit of a paint building the map (ok so not that bad).
Is there a simpler principle I can work on, or is that pretty much the best way to do it?
From the splendid Gamex
The best way I can think of is that a box gets coloured when a counter is zero, and the surrounding blocks decrease a particular counter (or counters for shared boxes). While this is simple enough it'll be a bit of a paint building the map (ok so not that bad).
Is there a simpler principle I can work on, or is that pretty much the best way to do it?
Post edited by R-Tape on
Comments
http://www.worldofspectrum.org/infoseekid.cgi?id=0005395
It may give you good hints, it seems to take into account number of moves and number of changes of direction
JSpeccy-win32-portable
I would first create a data structure for boxes with easy neighbour detection. And then for each box (starting with top-left and moving down to bottom-right) try to "get out" via neighbours that are not surrounded. If I don't make it then the box (and entire path i.e. all boxes on the way) are surrounded. A simple flood fill algorithm should do the job.
Here's the routine, anyway. Note that it uses OR to flag the corners, so they can be entered many times but only get marked once. Each rectangle's marker byte will be set to 15 when all four corners have been entered.
;corner coordinate table: marker, row,col, row,col, row,col, row,col CORNERS:DEFB 0, 1,1, 1,10, 8,1, 8,10 DEFB 0, 3,10, 3,20, 12,10, 12,20 DEFB 0, 8,20, 8,28, 12,20, 12,28 DEFB 16 CountCorners: ld ix,CORNERS-9 ld bc,(23670) ;BC=(SEED) NextRectangle: ;row,col coords in B,C ld de,9 add ix,de push ix pop hl ld a,15 cp (hl) jr z,NextRectangle ;skip if already filled ret c ;end of table inc a NextCorner: srl a ;shift marker, starts at %00001000 jr c,NextRectangle inc hl ld d,(hl) ;row inc hl ld e,(hl) ;col ex de,hl sbc hl,bc ;Carry reset by SRL ex de,hl jr nz,NextCorner GotCorner: or (ix+0) ;use OR to avoid marking the same corner twice ld (ix+0),a cp 15 jr nz,NextRectangle ;all 4 corners entered ;... fill rectangle ... jr NextRectangleDeal with edges instead of vertices. A box is made of four edges. An edge is visited if the last two vertices visited define the edge. From that picture it looks like the boxes are polygons with more than four edges.
Write games in C using Z88DK and SP1
As you say, the only certain way to determine enclosure is to count the edges completed. I was thinking of defining the ends of each distinct edge (which would be 34 in this picture, as the centre block has common vertical edges with the blocks either side) x 2 for row+col = 68 bytes (Table A). Then define which four edges enclose each box, 4 x 9 = 36 bytes (Table B). Then, as the maximum length of an edge seems to be 8 character squares, each distinct edge could have one marker byte with the bits set for each position along its length which has been entered = 34 bytes (Table C) - some bits would be pre-set where the length is less than 8.
Then, after each move, set the bit in Table C for each edge in Table A which contains that position, then check which boxes in Table B contain those edges, then check the 4 marker bytes in Table C for each of those boxes. If all four marker bytes for a box = 255 then that box is enclosed and can be filled. A Table D could also be used to flag filled boxes, so they only get filled once.
Tables A+C could be combined, as could tables B+D. It all seems a bit of a palaver though. The corner method was much simpler & neater, but it would produce false positives. I wonder if it would be possible to add a false positive check to the corner method?
--
Shame there aren't just 8 boxes, as then it would just need 'n' bytes for the xref list, as the individual bits could be set for the box numbers.
--
Oh, hang on, that could be done by having a separate mini-table for the centre box. So the outer boxes are numbered 0-7 for their bit positions in the bytes of the xref list. The central box just has a simple list of its border squares. To simplify the main xref lookup the list could be a fixed 768 bytes then just use row*32+col to get the entry. The mini-table would just have a list of numbers in the range 0-767 indicating which of the main list squares constitute its border.
If you pass through vertex A on the way to B but turn around and pass through vertex A again, the last two vertices are A,A. If you don't ignore duplicate passes, there is no problem with this. But the image shown shows rectangles staggered which is why I mentioned, these may actually be polygons with more than four edges. The same idea applies but each box can have more than four edges.
Like your idea above, a box/polygon can keep a count of edges still live and when one of its edges is painted, that count is decreased with reaching zero meaning it's time to fill it.
Write games in C using Z88DK and SP1
- IONIAN-GAMES.com -
I should say it's not really about processing time and I shouldn't have used the word clunky (also not specific to the picture example, just any painter game). I was mainly wondering about alternative ways to do it, seemingly there is no magic solution and the two main ways are:
1 - Use blocks, different block types surround the box and each one decreases one or more counters depending on which boxes they touch. Setting the counters and placing the blocks in a map would be a bit faffy if done manually, though could be automated without toooo much difficulty. I quite like this one as it avoids the need for the boxes to be 'smart objects', other than 'fill box when box counter n is zero'.
2 - Have the boxes as 'smart objects', they know how big they are and check all the way around for set blocks. Probably less faff to automate.
Thanks again all, I'm not sure I'll end up using this idea yet, especially as I've realised just how rusty I've become!
Lets say you can keep it below 255 spots along the paths (shouldn't be too hard). On a screen grid (less than 1K) are the number of each path spot, or 0 for non-pathways. Those numbers get multiplied by four and applied to a longer list (1K) which can then, for each spot, list up to four box numbers to decrement. It's fast, but the pain is preparing it all.
- IONIAN-GAMES.com -
Boxes.Corners
org 32768 ;corner coordinate table: ;TopL:row,col, TopR:row,col, BotL:row,col, BotR:row,col, counter defw Initialise, CountSquares CORNERS:DEFB 1,1, 1,8, 8,1, 8,8, 0 defb 2,8, 2,15, 8,8, 8,15, 0 defb 1,15, 1,22, 8,15, 8,22, 0 defb 8,2, 8,9, 15,2, 15,9, 0 defb 8,9, 8,14, 15,9, 15,14, 0 defb 8,14, 8,21, 15,14, 15,21, 0 defb 15,1, 15,8, 22,1, 22,8, 0 defb 15,8, 15,15, 21,8, 21,15, 0 defb 15,15, 15,22, 22,15, 22,22, 0 DEFB $ffBoxes.InitialiseInitialise: ;calculate the size of each border; call once ld ix,CORNERS-9 Loop1: ld de,9 add ix,de ld a,(ix+0) cp $ff ret z ld a,(ix+3) ;A =right col sub (ix+1) ; -left col add a,a ; *2 ld b,a ld a,(ix+4) ;A =bottom row sub (ix+0) ; -top row add a,a ; *2 add a,b ld (ix+8),a ;A =size of border ld b,(ix+0) ld c,(ix+1) ;BC=TopL:row,col call GetAttrLoc ld a,(ix+4) ;A =BotL:row sub b ld b,a ;B =row diff push bc push hl ld a,(ix+3) ;A =TopR:col inc a sub c ld c,a ;C =number of cols ld d,b xor a srl d rra srl d rra srl d rra ld e,a add hl,de ex de,hl ;DE=bot row pointer pop hl ;HL=top row pointer push hl ld a,16 ld b,c ;B =number of cols Loop2: ld (hl),a ;draw a red box border ld (de),a inc hl inc de djnz Loop2 dec hl ;HL=R col pointer pop de ;DE=L col pointer ld a,16 ld bc,32 ex af,af' pop af ;A =row diff Loop3: ex af,af' ld (hl),a ;draw a red box border ld (de),a add hl,bc ex de,hl add hl,bc ex de,hl ex af,af' dec a jr nz,Loop3 jp Loop1Boxes.CountSquaresCountSquares: ;check for enclosure; call after each move ld ix,CORNERS-9 ld bc,(23680) ;row,col coords in B,C call GetAttrLoc ld a,(hl) and %0011100 cp 8 ret z ;PAPER already blue, nothing to do cp 16 ret nz ;PAPER not red, nothing to do ld a,(hl) sub 8 ld (hl),a ;PAPER change from red to blue NextBox: ld de,9 add ix,de ld a,(ix+0) ;A =top row cp $ff ret z ;end of table cp b jr z,GotHrow ld a,(ix+4) ;A =bottom row cp b jr z,GotHrow ld a,(ix+1) ;A =left col cp c jr z,GotVcol ld a,(ix+3) ;A =right col cp c jr z,GotVcol jr NextBox GotHrow:;on either top or bottom row ld a,(ix+1) ;A =left col dec a cp c jr nc,NextBox ;too small ld a,(ix+3) ;A =right col cp c jr c,NextBox ;too big jr InBorder GotVcol:;on either left or right col ;don't count top & bottom corners, already counted in GotHrow ld a,(ix+0) ;A =top row cp b jr nc,NextBox ;too high ld a,(ix+4) ;A =bottom row dec a cp b jr c,NextBox ;too low InBorder: dec (ix+8) jp nz,NextBox ;fill box push bc ld b,(ix+0) ld c,(ix+1) ;BC=TopL:row,col inc b inc c call GetAttrLoc ;HL=top left inner corner address ld a,(ix+6) ;A =BotR:row sub b ; -TopL:row ld d,a ;D =number of rows inside box ld a,(ix+7) ;A =BotR:col sub c ; -TopL:col ld e,a ;E =number of cols inside box Loop4: ld b,e push hl Loop5: ld (hl),24 ;PAPER magenta inc hl djnz Loop5 pop hl ld bc,32 add hl,bc dec d jr nz,Loop4 pop bc jp NextBox GetAttrLoc: ;calculate attribute address for row,col B,C ld h,b xor a srl h rra srl h rra srl h rra or c ld l,a ld a,h or $58 ld h,a ;(HL)=ATTR(B,C) retI'm sure there is a way to do the the per pixel case using that fact too, and you can calculate which side to mark as part of the loop by counting how many clockwise and anticlockwise turns you make when you complete a loop (if you make more clockwise turns, you fill to the right of the way you are facing, otherwise fill on the left). But I'm drinking and playing Dark Souls at the mo, keep falling into the deep water fighting a hydra.
I'll think about it some more tomorrow and may post in maths & physics on gamedev if I can't work it out. Deciding which paths (and hence which turns to add up for the clockwise/anticlockwise check) form the perimeter is my main concern.
CountSquares does that preliminary check and exits straight away if it doesn't need to do anything. The counter for each box is set to the length of its border. When moving onto a red square the square is changed to blue and the counter for each box which contains that square in its border is decremented. When a box's counter reaches zero it is filled. Nothing else needs to be considered.
It's slightly more complicated if the boxes have more than four corners, but then just divide the meta-box into boxes which do have four corners and fill it when all its counters run down to zero - or have a meta-box counter which holds the number of constituent boxes, decremented each time one of its box counters runs down to zero, and filled when its meta-counter runs down to zero.
Any thought about the general case then? If you always turn left and end up where you have already been, you have enclosed an area anticlockwise, and the interior is on your left when you finish the loop. If you turn left more than you turn right, you still traced out an anticlockwise area (I think, I'll have to get out a pencil - EDIT: I'm pretty sure that is the case). Problem is when you have more paths and some areas already filled. It would be nice if there was a method that didn't have to enumerate all the possible paths (i.e. each turn at an intersection), I'll have to think about that too.
EDIT: Something along those lines should work for non convex regions, with an arbitrary field size, is what I am thinking.
EDIT2: You have to be able to move in non orthogonal directions (i.e. diagonal) to have more than 4 regions adjoining any given node. 4 is the worst case all others are T-junctions or corridors. Or dead ends, they don't really work with this sort of game!
* The screen is divided into a number of boxes.
* Boxes may be of varying shapes & sizes.
* Each box has a border.
* Boxes and borders are made up of ... errmmm ... blocks.
* Some parts of a box's border may be shared by other boxes.
* Movement is restricted to the borders but not otherwise.
* Setup defines each box's dimensions & each border's empty length.
* All border blocks are initially marked "empty" (eg. by colour).
* Each time an empty border block is entered it is marked "full" (eg. by changing colour).
* Each time a border block is marked "full" the empty length counter for each box which contains that block in their border is decremented.
* Each time a box's border's empty length runs down to zero (ie. it is full) then the box enclosed by this border is also filled. (Thus filling a shared border block might trigger the filling of more than one box.)
* When all the boxes have been filled the screen is complete.
The End
My thoughts are we need to have each pixel marked as either not traversed, traversed, or part of an interior region, so needing at least 2 bits of storage per pixel (=node). We could create nodes dynamically when we change direction if we wanted.
EDIT: I'm thinking of the classic painter game where you build paths as you go along, there are no set paths to traverse when you begin a level. Which makes a big difference ;) EDIT2: Maybe that's not how the original painter game worked (I think not, it did have set routes for you to travel on)? That's the problem I am thinking about though... Mathematician lol.
EDIT2: Which is, how do you detect you have enclosed all regions of a 2D space (rectangular probably, but that doesn't really matter) when tracing a path. Any closed area is considered completed. It's easy to detect when you have filled the whole area, count the number of pixels inside the closed regions.
EDIT3: Your method will work for any shape if the paths are predefined, you can just preprocess each level. You can just check all the points between straight line nodes of the graph to verify you have visited all points along the path.
Yes, that was my idea. If the player can just wander around all over the place until they find their own tail then it's rather more difficult.
I'm sure there is a solution to the problem if you make the network as you travel along, it probably involves building a network dynamically and doing a graph search.