<s> """<STR_LIT>""" <EOL> import numpy <EOL> import networkx as nx <EOL> from pelita . datamodel import north , south , east , west <EOL> W = b'<STR_LIT:#>' <EOL> F = b'<STR_LIT:.>' <EOL> E = b'<STR_LIT:U+0020>' <EOL> def empty_maze ( height , width ) : <EOL> """<STR_LIT>""" <EOL> maze = numpy . empty ( ( height , width ) , dtype = '<STR_LIT:c>' ) <EOL> maze . fill ( E ) <EOL> maze [ <NUM_LIT:0> , : ] . fill ( W ) <EOL> maze [ - <NUM_LIT:1> , : ] . fill ( W ) <EOL> maze [ : , <NUM_LIT:0> ] . fill ( W ) <EOL> maze [ : , - <NUM_LIT:1> ] . fill ( W ) <EOL> return maze <EOL> def maze_to_str ( maze ) : <EOL> """<STR_LIT>""" <EOL> lines = [ b'<STR_LIT>' . join ( maze [ i , : ] ) <EOL> for i in range ( maze . shape [ <NUM_LIT:0> ] ) ] <EOL> return b'<STR_LIT:\n>' . join ( lines ) <EOL> def str_to_maze ( str ) : <EOL> """<STR_LIT>""" <EOL> maze = numpy . array ( [ list ( ln . strip ( ) ) for ln in str . splitlines ( ) <EOL> if len ( ln . strip ( ) ) > <NUM_LIT:1> ] ) <EOL> return maze <EOL> def create_half_maze ( maze , ngaps_center ) : <EOL> """<STR_LIT>""" <EOL> ch = maze . shape [ <NUM_LIT:0> ] - <NUM_LIT:2> <EOL> candidates = numpy . random . permutation ( ch // <NUM_LIT:2> ) <EOL> half_gaps_pos = candidates [ : ngaps_center // <NUM_LIT:2> ] <EOL> gaps_pos = [ ] <EOL> for pos in half_gaps_pos : <EOL> gaps_pos . append ( pos ) <EOL> gaps_pos . append ( ch - pos - <NUM_LIT:1> ) <EOL> _add_wall_at ( maze , ( maze . shape [ <NUM_LIT:1> ] - <NUM_LIT:2> ) // <NUM_LIT:2> - <NUM_LIT:1> , ngaps_center , <EOL> vertical = True , gaps_pos = gaps_pos ) <EOL> _add_wall ( maze [ : , : maze . shape [ <NUM_LIT:1> ] // <NUM_LIT:2> ] , ngaps_center // <NUM_LIT:2> , vertical = False ) <EOL> def _add_wall_at ( maze , pos , ngaps , vertical , gaps_pos = None ) : <EOL> """<STR_LIT>""" <EOL> if not vertical : <EOL> maze = maze . T <EOL> center = maze [ <NUM_LIT:1> : - <NUM_LIT:1> , <NUM_LIT:1> : - <NUM_LIT:1> ] <EOL> ch , cw = center . shape <EOL> center [ : , pos ] . fill ( W ) <EOL> ngaps = max ( <NUM_LIT:1> , ngaps ) <EOL> if gaps_pos is None : <EOL> gaps_pos = numpy . random . permutation ( numpy . arange ( ch ) ) . tolist ( ) <EOL> gaps_pos = gaps_pos [ : ngaps ] <EOL> if maze [ <NUM_LIT:0> ] [ pos + <NUM_LIT:1> ] == E : <EOL> gaps_pos . insert ( <NUM_LIT:0> , <NUM_LIT:0> ) <EOL> if maze [ - <NUM_LIT:1> ] [ pos + <NUM_LIT:1> ] == E : <EOL> gaps_pos . insert ( <NUM_LIT:0> , ch - <NUM_LIT:1> ) <EOL> for gp in gaps_pos : <EOL> center [ gp , pos ] = E <EOL> sub_mazes = [ maze [ : , : pos + <NUM_LIT:2> ] , maze [ : , pos + <NUM_LIT:1> : ] ] <EOL> if not vertical : <EOL> sub_mazes = [ sm . T for sm in sub_mazes ] <EOL> return sub_mazes <EOL> def _add_wall ( maze , ngaps , vertical ) : <EOL> """<STR_LIT>""" <EOL> h , w = maze . shape <EOL> center = maze [ <NUM_LIT:1> : - <NUM_LIT:1> , <NUM_LIT:1> : - <NUM_LIT:1> ] <EOL> ch , cw = center . shape <EOL> if ch < <NUM_LIT:3> and cw < <NUM_LIT:3> : <EOL> return <EOL> size = cw if vertical else ch <EOL> min_size = numpy . random . randint ( <NUM_LIT:3> , <NUM_LIT:6> ) <EOL> if size >= min_size : <EOL> pos = numpy . random . randint ( <NUM_LIT:1> , size - <NUM_LIT:1> ) <EOL> sub_mazes = _add_wall_at ( maze , pos , ngaps , vertical ) <EOL> for sub_maze in sub_mazes : <EOL> _add_wall ( sub_maze , max ( <NUM_LIT:1> , ngaps // <NUM_LIT:2> ) , not vertical ) <EOL> def walls_to_graph ( maze ) : <EOL> """<STR_LIT>""" <EOL> h , w = maze . shape <EOL> graph = nx . Graph ( ) <EOL> for x in range ( w ) : <EOL> for y in range ( h ) : <EOL> if maze [ y , x ] != W : <EOL> graph . add_node ( ( x , y ) ) <EOL> directions = [ west , east , north , south ] <EOL> nodes = graph . nodes ( ) <EOL> for pos in nodes : <EOL> for dir_ in directions : <EOL> neighbor = ( pos [ <NUM_LIT:0> ] + dir_ [ <NUM_LIT:0> ] , pos [ <NUM_LIT:1> ] + dir_ [ <NUM_LIT:1> ] ) <EOL> if neighbor in nodes : <EOL> graph . add_edge ( pos , neighbor , data = [ dir_ ] ) <EOL> return graph , nodes [ <NUM_LIT:0> ] <EOL> def find_dead_ends ( graph , start_node , width ) : <EOL> """<STR_LIT>""" <EOL> dead_ends = [ ] <EOL> def collect_dead_ends ( node ) : <EOL> x = node [ <NUM_LIT:0> ] <EOL> if graph . degree ( node ) == <NUM_LIT:1> and x < width - <NUM_LIT:1> : <EOL> dead_ends . append ( node ) <EOL> for node in nx . bfs_successors ( graph , start_node ) : <EOL> collect_dead_ends ( node ) <EOL> return dead_ends <EOL> def remove_dead_end ( dead_node , maze ) : <EOL> """<STR_LIT>""" <EOL> h , w = maze . shape <EOL> pos = dead_node . data <EOL> free_dir = dead_node . get_edges_out ( ) [ <NUM_LIT:0> ] . data [ <NUM_LIT:0> ] <EOL> free_to_pierce = { west : [ east , north , south ] , <EOL> east : [ west , north , south ] , <EOL> north : [ south , west , east ] , <EOL> south : [ north , west , east ] <EOL> } <EOL> for pierce_dir in free_to_pierce [ free_dir ] : <EOL> pierce_x , pierce_y = pos [ <NUM_LIT:0> ] + pierce_dir [ <NUM_LIT:0> ] , pos [ <NUM_LIT:1> ] + pierce_dir [ <NUM_LIT:1> ] <EOL> if ( pierce_x >= <NUM_LIT:0> and pierce_x < w - <NUM_LIT:1> <EOL> and pierce_y >= <NUM_LIT:0> <EOL> and pierce_y < h ) : <EOL> maze [ pierce_y , pierce_x ] = E <EOL> break <EOL> def remove_all_dead_ends ( maze ) : <EOL> height , width = maze . shape <EOL> while True : <EOL> maze_graph , start_node = walls_to_graph ( maze [ <NUM_LIT:1> : height - <NUM_LIT:1> , <EOL> <NUM_LIT:1> : width // <NUM_LIT:2> ] ) <EOL> dead_ends = find_dead_ends ( maze_graph , <EOL> start_node , width // <NUM_LIT:2> - <NUM_LIT:1> ) <EOL> if len ( dead_ends ) == <NUM_LIT:0> : <EOL> break <EOL> remove_dead_end ( dead_ends [ <NUM_LIT:0> ] , maze [ <NUM_LIT:1> : height - <NUM_LIT:1> , <NUM_LIT:1> : width // <NUM_LIT:2> ] ) <EOL> def add_pacman_stuff ( maze , max_food ) : <EOL> """<STR_LIT>""" <EOL> h , w = maze . shape <EOL> maze [ - <NUM_LIT:2> , <NUM_LIT:1> ] = '<STR_LIT:2>' <EOL> maze [ - <NUM_LIT:3> , <NUM_LIT:1> ] = '<STR_LIT:0>' <EOL> maze [ <NUM_LIT:1> , - <NUM_LIT:2> ] = '<STR_LIT:3>' <EOL> maze [ <NUM_LIT:2> , - <NUM_LIT:2> ] = '<STR_LIT:1>' <EOL> total_food = <NUM_LIT:0> <EOL> while total_food < max_food : <EOL> row = numpy . random . randint ( <NUM_LIT:1> , h - <NUM_LIT:1> ) <EOL> col = numpy . random . randint ( <NUM_LIT:1> , ( w // <NUM_LIT:2> ) - <NUM_LIT:1> ) <EOL> if ( row > h - <NUM_LIT:6> ) and ( col < <NUM_LIT:6> ) : continue <EOL> if maze [ row , col ] == E : <EOL> maze [ row , col ] = F <EOL> maze [ h - row - <NUM_LIT:1> , w - col - <NUM_LIT:1> ] = F <EOL> total_food += <NUM_LIT:2> <EOL> def get_new_maze ( height , width , nfood = <NUM_LIT:30> , seed = None , dead_ends = False ) : <EOL> """<STR_LIT>""" <EOL> if seed is None : <EOL> seed = numpy . random . randint ( <NUM_LIT:1> , <NUM_LIT:2> ** <NUM_LIT> - <NUM_LIT:1> ) <EOL> numpy . random . seed ( seed ) <EOL> maze = empty_maze ( height , width ) <EOL> create_half_maze ( maze , height // <NUM_LIT:2> ) <EOL> maze [ - <NUM_LIT:2> , <NUM_LIT:1> ] = E <EOL> maze [ - <NUM_LIT:3> , <NUM_LIT:1> ] = E <EOL> if not dead_ends : <EOL> remove_all_dead_ends ( maze ) <EOL> maze [ : , width // <NUM_LIT:2> : ] = numpy . flipud ( numpy . fliplr ( maze [ : , : width // <NUM_LIT:2> ] ) ) <EOL> add_pacman_stuff ( maze , max_food = <NUM_LIT:2> * nfood ) <EOL> return maze_to_str ( maze ) </s>
