/* AWM_TO_REGIONS.P */ section awm_to_regions => awm_to_regions; /* SPECIFICATION ------------- This module exports a routine for marking regions within an AWM. The idea is best shown by an example: awm => ** AWM: xk: -5 to 5; yk: -5 to 5 xbounds: -10 to 10; ybounds: -10 to 10 position: (0,0) forward: [0 1]; right: [1 0] ??? ??? ???*****??? ??? ??? * k * * * * B # * * * * * ???*****??? ??? ??? ???@ ??? awm_to_regions( awm, `a`, procedure(c);1+c;endprocedure, true ) -> regions; awm=> ** AWM: xk: -5 to 5; yk: -5 to 5 xbounds: -10 to 10; ybounds: -10 to 10 position: (0,0) forward: [0 1]; right: [1 0] ???eeeee??? ???*****??? ???ccccc??? bb*ccckcc*d bb*cccccc*d bb*ccBccc#d bb*cccc*c*d bb*cccccc*d ???*****??? ???aaaaa??? ???@aaaa??? regions==> ** [[101 [-2 5] [-1 5] [0 5] [1 5] [2 5]] [100 [5 -2] [5 -1] [5 0] [5 1] [5 2]] [99 [-2 -2] [-2 -1] [3 2] [2 3]] [98 [-5 -2] [-5 -1] [-4 -2] [-4 2]] [97 [-1 -5] [-2 -4] [-1 -4] [0 -5] [0 -4] [1 -5] [1 -4] [2 -5] [2 -4]]] Essentially, within an AWM, awm_to_regions finds all the regions (connected regions of blank squares, bounded by non-spaces or undefineds), and replaces all the blanks in each with a unique character. It also returns a list of these characters and the points making up each region. The marked AWM can be used in various types of analogical processing. For example, to find out what region an object is in, you only need to look at the region markers neighbouring it. PUBLIC awm_to_regions( awm, first_reg, next_reg, keep ): This routine marks awm in the way described above. first_reg must be a character, to be used as the marker for the first region found. next_reg must be a function which when applied to a region marker, yields the next one. In the example above, this is done just by adding one to it. If keep is true, awm_to_regions returns a list of sublists. Each sublist is of the form [ ... ] where is that region's character, and etc are the points within the region, as vecs (or lists: see HELP VEC). If keep is true, awm_to_regions just returns an integer, giving the number of regions found. Resetting an AWM ---------------- You can use the routine awm_replace from AWM.P to get rid of the region markers. In the example above, the call awm_replace( awm, procedure(c);lvars c; c>=`a`;endprocedure, ` ` ); will replace any character whose ASCII code is that for `a` or greater, with a space. */ /* IMPLEMENTATION -------------- I use a brute-force method. awm_to_regions runs through its awm argument, examining every character in turn. If this character is blank, it calls flood to replace it and all the blanks connected to it by a region marker. It then restarts the scan. It should be possible to make this more efficient by not examining characters which have been flooded out. I haven't thought about how to do this. This module has a HELP file, HELP AWM_TO_REGIONS. Keep it in step with the code. */ needs awm; vars flood;/*forward*/ define awm_to_regions( awm, first_reg, next_reg, keep ); lvars awm, first_reg, next_reg, keep; lvars i=awm.awm_x_known_min, j=awm.awm_y_known_min; lvars reg=first_reg, regno=0, regions = []; /* Scans from one beyond the location of the last-scanned character, i.e. (i+1,j) for a c. If found, set (i,j) to its location and return true, else return false. */ define scan_until(c); lvars c; lvars x=i+1, y=j; repeat if x > awm.awm_x_known_max and y > awm.awm_y_known_max then return(false) endif; if x > awm.awm_x_known_max then awm.awm_x_known_min->x; 1+y->y; nextloop; endif; if awm(x,y) = c then x->i; y->j; return(true) else 1+x->x; endif; endrepeat; enddefine; while scan_until(` `) do 1 + regno -> regno; if keep then [ [ ^reg ^^([%flood(awm,reg,i,j,keep)%]) ] ^^regions ] -> regions; else flood(awm,reg,i,j,keep) endif; next_reg(reg) -> reg; endwhile; if keep then regions else regno endif; enddefine; /* flood( awm, c, i, j, keep ): Starting at awm(i,j), which should be blank, fill it and all squares connected thereto with a c. We use depth-first search to do this, implemented by recursive calls to flood within awm_app_neighbours. If the recursion depth grows too big, we could use depth-first search from SEARCH.P instead. */ define flood( awm, c, i, j, keep ); lvars awm, c, i, j, keep; if awm(i,j) = ` ` then c -> awm(i,j); if keep then [% i, j %] endif; awm_app_neighbours( awm, i, j, procedure(awm,x,y); lvars awm, x, y; if awm(x,y) = ` ` then flood(awm,c,x,y,keep) endif endprocedure ) endif; enddefine; endsection;