D ATA S TRUCTURES AND A LGORITHMS Introduction: you are required to simulate a m

Question

DATA STRUCTURES AND ALGORITHMS

Introduction: you are required to simulate a maze traversal, i.e. you need to develop a program that starts from some location in a maze, and searches it to locate an exit.

The maze should be implemented as a two-dimensional array of characters, where #s represent walls of the maze, whitespace characters represent empty spaces in the maze through which one can walk. In the maze, you can move one step at a time in the following four directions: up, down, right, left — no “diagonal” moves are allowed. A move can be made only to a location in the array that contains a whitespace.

Figure_1.

If there is an exit the program finds way out and displays the solution as described below. See Figure_2 and Figure_3.

If there is no way out of the maze, the program should report that there is no solution.

1.The implementation requirements.

1.1. A maze should be implemented as a 2-dimensional square (nn) array of characters. The only allowed characters in the array are:

•'#' — denote walls of the maze;

•' ' — denote unvisited locations in the maze;

•'x' — denote visited locations, that are not yet "dead ends";

•'d' — "dead ends", i.e. locations from which you cannot proceed further and should return back.

Initially the array(maze) contains only '#' s and ' 's.

1.2. You will need to define a struct location to represent locations in the maze and a stack to store visited locations.

1.3. To solve a maze you need to implement the following (recursive) algorithm:

(a)Start from some initial location in the maze that contains a whitespace, i.e. push it on the stack. Proceed to (b).

(b)If the top location on the stack contains a whitespace, override it by 'x'.

•if this location is an exit proceed to (e).

•else proceed to (c).

(c)Try one by one locations adjacent to the top location on the stack. (up, down, left, right).

•push on stack the first one that contains a whitespace. Proceed to (b).

•else, if none of the adjacent locations contain a whitespace, override the top location's character by 'd' and pop the stack.

•if the stack is empty proceed to (d).

•else proceed to (c).

(d) Print "There is no solution", then exit.

(e). Print the found solution in a nice format like the one on Figure_3, then exit. Note, that the solution path is contained in the stack.

2. The main function.

In the main function you have to test your program against two different mazes:

•The one from Figure_2 (with the specified initial position). Please note, that your program may output a different solution.

•Design a maze nn, n > 10, and solve it.

Submission:

•            successful compilation

•            successful completion the required tasks

•            adherence to the guidelines provided

•            quality of code that adheres to the programming standards for the Course; including:

•            comments and documentation

1.           code layout

2.           meaningful variable names

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <stl.h>
#include <hash_set>

#include "maze.h"
#include "grid.h"
#include "cmumovie.h"

float RUBIN_CONST=1.1;

extern int global_movie_expand;
extern vector<list<wire_segment> > net_paths_segment;
extern vector<int> vi_violations;
long long cells_expanded=0;
int nets_routed=0;
int dir_cost=10;
int via_cost=10;
int bend_cost=1;
int global_num_cells_frame=10;
int dir_cost_array[4][6];

list<cell> maze_route(grid &g, list<cell> &source, int net_dest,
list<pin> &remaining);

bool operator<(const active_cell &ac, const active_cell &ac2)
{
return (ac.total_cost>ac2.total_cost);
}


static int estimated_pathcost(cell c, cube r)
{
int dx=0,dy=0,dz=0;

if (c.x < r.x1) {
dx=r.x1-c.x;
} else if (c.x > r.x2) {
dx=c.x - r.x2;
}

if (c.y < r.y1) {
dy=r.y1-c.y;
} else if (c.y > r.y2) {
dy=c.y-r.y2;
}

if (c.l < r.z1) {
dz=r.z1 - c.l;
} else if (c.l > r.z2) {
dz=c.l-r.z2;
}

return dx+dy+dz*(via_cost);
}

// estimated path cost for a destination pin
// to a source cube -- how to deal with levels
static int estimated_pathcost(pin p, cube r)
{
int dx=0,dy=0,dz=0;

if (p.x < r.x1) {
dx=r.x1-p.x;
} else if (p.x > r.x2) {
dx=p.x - r.x2;
}

if (p.y < r.y1) {
dy=r.y1-p.y;
} else if (p.y > r.y2) {
dy=p.y-r.y2;
}

// pins have no level information
/*
if (p.l < r.z1) {
dz=r.z1 - p.l;
} else if (p.l > r.z2) {
dz=p.l-r.z2;
}
*/

// return dx+dy+dz*(via_cost+1);
return dx+dy;
}


static cube get_bounding_cube(list<pin> &vp)
{
int i,count=0;
int vp_size=vp.size();
cube r;
r.x1=vp.front().x;
r.x2=vp.front().x;
r.y1=vp.front().y-1;
r.y2=vp.front().y+1;

list<pin>::iterator lpi;
lpi=vp.begin();
++lpi;
for (;lpi!=vp.end();++lpi,++count) {
if (lpi->x<r.x1) r.x1=lpi->x;
if ((lpi->x)>r.x2) r.x2=(lpi->x);
if ((lpi->y-1)<r.y1) r.y1=(lpi->y-1);
if ((lpi->y+2)>r.y2) r.y2=(lpi->y+1);
}
r.z1=0;
r.z2=1;
return r;
}

// cells from pin cannot be in lc to begin with
static void add_cells_from_pin(list<cell> &lc, pin p)
{
int y;
int l=-1,h=1;

if (p.pad) {
l=0;h=0;
}

cell c;

for (y=l;y<=h;y++) {
c.x=p.x;
c.y=p.y+y;
c.l=1;
c.l2=-1;
lc.push_back(c);
c.l=0;
lc.push_back(c);
}
}

int get_seg_dir(wire_segment ws)
{
if (ws.x1==ws.x2 && ws.y1==ws.y2) {
if ((ws.z1-ws.z2)==1) return 0;
if ((ws.z2-ws.z1)==1) return 1;
return -2; // up/down
}
if (ws.x1==ws.x2 && ws.z1==ws.z2) {
if ((ws.y1-ws.y2)==1) return 2;
if ((ws.y2-ws.y1)==1) return 3;
return -2; // north/south
}
if (ws.y1==ws.y2 && ws.z1==ws.z2) {
if ((ws.x1-ws.x2)==1) return 4;
if ((ws.x2-ws.x1)==1) return 5;
return -2; // east/west
}
return -2;
}

void segment_to_path(list<wire_segment> &path, list<cell> &ret)
{
cell c;

list<wire_segment>::iterator lwsi;
for (lwsi=path.begin();lwsi!=path.end();++lwsi) {
if (lwsi->z1==lwsi->z2) { // not a via
if (lwsi->x1 != lwsi->x2) { // x dir
c.y=lwsi->y1;
c.l=lwsi->z1;
for (c.x=min(lwsi->x1,lwsi->x2);
c.x<=(max(lwsi->x1,lwsi->x2));c.x++)
ret.push_back(c);
} else { // y dir
c.x=lwsi->x1;
c.l=lwsi->z1;
for (c.y=min(lwsi->y1,lwsi->y2);
c.y<=(max(lwsi->y1,lwsi->y2));c.y++)
ret.push_back(c);
}
}
}
}

list<wire_segment> path_to_segment(list<cell> &path)
{
list<wire_segment> ret;
wire_segment cur_seg,tseg;
int dir=-1;

cur_seg.x1=-1;
cur_seg.x2=-1;

list<cell>::iterator lci;
for (lci=path.begin();lci!=path.end();++lci) {
if (lci->l2>=0) { // we have a via
if (cur_seg.x2>=0) { // current segment is valid, so push it onto return list
ret.push_back(cur_seg);
}
cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l2;
ret.push_back(cur_seg);
cur_seg.x1=-1; cur_seg.x2=-1;
} else {
if (cur_seg.x1==-1) { //we have no current segment,
//new one will be just this cell
cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l;
dir=-1;
} else {
tseg.x1=cur_seg.x2; tseg.y1=cur_seg.y2; tseg.z1=cur_seg.z2;
tseg.x2=lci->x; tseg.y2=lci->y; tseg.z2=lci->l;
if (get_seg_dir(tseg)==-2) { //cells are not adjacent
ret.push_back(cur_seg);
cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l;
dir=-1;
} else {
if (dir==-1 || dir==get_seg_dir(tseg)) {
cur_seg.x2=lci->x;
cur_seg.y2=lci->y; cur_seg.z2=lci->l;
dir=get_seg_dir(tseg);
} else {
ret.push_back(cur_seg);
cur_seg=tseg;
dir=get_seg_dir(tseg);
}
}
}
}
}
if (cur_seg.x1!=-1) {
ret.push_back(cur_seg);
}
return ret;
}

list<pin> find_pin_to_route(list<pin> &remaining_pins, list<pin> &used_pins)
{
list<pin>::iterator lpi,best;
int pin_to_route_cost=1<<30;;
list<pin> pin_to_route;

cube source_cube = get_bounding_cube(used_pins);
for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
if (estimated_pathcost(*lpi,source_cube)<pin_to_route_cost) {
pin_to_route_cost = estimated_pathcost(*lpi,source_cube);
best = lpi;
}
}
pin_to_route.push_front(*best);
return pin_to_route;

}

list<cell> net_maze_route(grid &g, int net, list<pin> &pins, int &partial)
{
// we have to route each of the pins in turn until all the pins are
// connected

int pins_size=pins.size();
// for now we'll just do the pins in order
list<cell> source;
list<pin> remaining_pins=pins,used_pins;
list<cell> actual_paths;
int remaining_pins_size=remaining_pins.size();

list<pin> pin_to_route;

add_cells_from_pin(source,remaining_pins.front());
used_pins.push_back(remaining_pins.front());
remaining_pins.pop_front();
remaining_pins_size=remaining_pins.size();

while(!remaining_pins.empty()) {
list<pin>::iterator lpi,start_pin;
list<cell>::iterator lci;

pin_to_route = find_pin_to_route(remaining_pins,used_pins);
list<cell> path=maze_route(g,source,net,pin_to_route);
if (path.empty()) {
// printf("ERROR, no route to cell! ");
partial=1;
return actual_paths;
}

for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
if (lpi->x==path.back().x &&
(path.back().y>=(lpi->y-1) && path.back().y<=(lpi->y+1))) {
break;
}
}

if (lpi==remaining_pins.end()) {
printf("ERROR in net_maze_route... path doesn't end on ");
printf("one of the remaining pins! ");
printf("it ends at (%i,%i,%i) ",path.back().x,path.back().y,
path.back().l);
printf("remaining pins are: ");
for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
printf("(%i,%i,%i) ",lpi->x,lpi->y,0);
}

printf(" Source list is: ");
for (lci=source.begin();lci!=source.end();++lci) {
printf("(%i,%i,%i) ",lci->x,lci->y,lci->l);
}
printf(" Bad path is: ");
for (lci=path.begin();lci!=path.end();++lci) {
printf("(%i,%i,%i) ",lci->x,lci->y,lci->l);
}

exit(1);
}

add_cells_from_pin(source,*lpi);
used_pins.push_back(*lpi);
remaining_pins.erase(lpi);

// copy path to actual path
for (lci=path.begin();lci!=path.end();++lci)
actual_paths.push_back(*lci);

path.pop_front();
path.pop_back();

for (lci=path.begin();lci!=path.end();++lci) {
source.push_back(*lci);
}
//fprintf(stderr,"net_maze_route %i/%i ",used_pins.size(),
// remaining_pins.size());
//fflush(stderr);
}
partial=0;
return actual_paths;
}

void expand_cell(grid &g, priority_queue<active_cell> &pqa, cell &new_cell,
active_cell &ac, cube &dest_cube, char dir, int dest)
{
cells_expanded++;
active_cell nac;
nac.pathcost=ac.pathcost+1;
if (dest==0) nac.pathcost+=g.cellCost(new_cell);

// now we will check for bends

int old_dir=g.getPrevDir(ac.pos);
if (old_dir<4 && dir<4 && old_dir!=dir) nac.pathcost+=bend_cost;

// now we will check for vias
if (new_cell.l != ac.pos.l) nac.pathcost+=via_cost;

// let's penalize for the wrong direction:
// odd layers: north-south, even layers: east-west

if (new_cell.l&1) { // horizontal
if (dir==1 || dir==3) {
nac.pathcost+=dir_cost;
}
} else { // vertical
if (dir==0 || dir==2) {
nac.pathcost+=dir_cost;
}
}

// trying to add the heuristic fudge factor to
// make things go faster... turns out k=2 ended up being 10%
// faster than k=1, but much worse results
nac.total_cost=nac.pathcost+
(estimated_pathcost(new_cell,dest_cube))*RUBIN_CONST;

nac.pos=new_cell;

nac.dir=dir;
pqa.push(nac);

//fprintf(stderr,"reached cell (%i,%i,%i) path_cost=%.2f total_cost=%.2f ",
// nac.pos.x,nac.pos.y,nac.pos.l,nac.pathcost,
// nac.total_cost);

}

struct hash_cell_struct {
size_t operator() (const cell &c) const {
return c.x+c.y+c.l;
}
};

struct eqcell {
size_t operator() (const cell &a, const cell &b) const {
return (a.x==b.x && a.y==b.y && a.l==b.l);
}
};

hash_set<cell, hash_cell_struct, eqcell> get_destinations_from_pins(list<pin> &pins)
{
hash_set<cell, hash_cell_struct, eqcell> ret;

list<pin>::iterator lpi;
for (lpi=pins.begin();lpi!=pins.end();++lpi) {
cell c;
c.x=lpi->x;
for (c.l=0;c.l<2;c.l++) {
for (c.y=(lpi->y-1);c.y<=(lpi->y+1);c.y++) {
ret.insert(c);
}
}
}
return ret;
}

list<cell> maze_route(grid &g, list<cell> &source, int net_dest,
list<pin> &remaining_pins)
{
int i;
int count=0;
list<cell> vc;
list<cell> expanded_cells;

priority_queue<active_cell> pqa;

cube dest_cube;

g.clearVisitedAndPrev();
cell zero;
zero.x=-1;
zero.y=-1;
zero.l=0;

list<cell>::iterator lci;
// calc dest rectangle somehow
dest_cube = get_bounding_cube(remaining_pins);
hash_set<cell, hash_cell_struct, eqcell> destinations=
get_destinations_from_pins(remaining_pins);

for (lci=source.begin();lci!=source.end();++lci) {
if (lci->l2 >= 0) continue;
active_cell ac;
ac.pathcost=0;
ac.total_cost=estimated_pathcost(*lci,dest_cube)*RUBIN_CONST;
ac.pos=*lci;
ac.dir=7;
pqa.push(ac);
}

if (global_movie_expand) {
cmumovie_newframe();
cmumovie_drawnets(net_paths_segment,vi_violations);
cmumovie_drawsourcedest(source,remaining_pins);
}

while (!pqa.empty()) {
count++;
if (global_movie_expand && (count%global_num_cells_frame)==0) {
// draw an expanded cell movie frame
cmumovie_newframe_short();
//cmumovie_drawnets(net_paths_segment,vi_violations);
cmumovie_drawexpansion(expanded_cells);
expanded_cells.clear();
}
active_cell ac=pqa.top();
pqa.pop();
if (g.getVisited(ac.pos)) continue; // don't expand a cell twice
g.setVisited(ac.pos);
g.setPrev(ac.pos,ac.pos,ac.dir);
if (global_movie_expand) expanded_cells.push_back(ac.pos);
//fprintf(stderr,"expanding cell (%i,%i,%i) path_cost=%.2f total_cost=%.2f ",
// ac.pos.x,ac.pos.y,ac.pos.l,ac.pathcost,ac.total_cost);


// expanding cell ac
int done2=(destinations.find(ac.pos)!=destinations.end());
if (done2) {
// we have hit the target
// printf("We hit the target, backtracing ");
cell c=ac.pos;
unsigned char d;
do {
c.l2=-1;
vc.push_front(c);
d=g.getPrevDir(c);
if ((d==4) || (d==5)) {
if (d==4) c.l2=c.l-1;
if (d==5) c.l2=c.l+1;
vc.push_front(c);
}
} while ((c=g.getPrev(c)).x!=-1);
nets_routed++;
return vc;
}
int dir;
for (dir=0;dir<6;dir++) {
// printf("checking dir=%i ",dir);
cell new_cell;
if (g.getNeighbor(ac.pos,dir,new_cell) &&
!g.getVisited(new_cell)) {

int dest;
if (destinations.find(new_cell)!=destinations.end())
dest=1;
else dest=0;
expand_cell(g,pqa,new_cell,ac,
dest_cube,dir,dest);
//}
}
}
}
return vc; // no path found, return empty
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.