Class Maze- Maze.h, Maze.cc


 
Definition:
A Maze is used to perform maze routing.  In its true form, maze routing can only be done with two terminal nets though it is often extended to handle multi-terminal nets.  This maze router can handle multiple pin (terminals) in that it will remember the routing from previous Steiner edges and abort the routing if it intersects a previous edge.  The 'edges' of the maze are stored in the RouteTracks data structure.  The points are stored in a vector of vectors of MazePoints.
Typedefs:
typedef vector<MazePoint *> ColumnVector;
typedef ColumnVector::iterator ColumnVectorItr;
typedef vector<ColumnVector *> MazeVector;
typedef MazeVector::iterator MazeVectorItr;
typedef priority_queue<MazePoint *,vector<MazePoint *>,PointCompare> PriorityQ;
typedef list<MazePoint *> MazeList;
typedef MazeList::iterator MazeListItr;
Included:
#include "MazePoint.h"
#include "Net.h"
#include "PrimMST.h"
#include "RouteTracks.h"
#include <iostream.h>
#include <vector>
#include <queue>
#include <list>


Variable Index
 
o int x
The number of points along the x-axis i.e. the width of the maze.
o int y
The number of points along the y-axis i.e. the height of the maze.
o bool sinkFound
A boolean variable indicating whether the maze routing is complete i.e. the sink has been located.
o MazeVector * maze
A 'vector of vectors of maze points' or 2-dimensional vector.  The first vector indexes the column (x-axis) of the maze point and the second set of vectors indexs the y-axis value of the point.
oPoint * source
The source point.  The maze router begins its expansion from this point.
oPoint * sink
The sink point.  The end point of the router.  The maze router is searching for this point and completes when it finds it.
o ProiorityQ * costQ
A priority queue used to determine which points are to be searched next.  The points in the queue are popped according to some function which is defined in the class PointCompare -- an internal class within this class.
o MazeList * possibleRoutePts
I don't think that this does anything...
o MazeList * routePts
This doesn't seem to have any purpose now though I'm not sure.  Probably left over from an earlier implementation.
oNet * mazeNet
The net that is being routed.
oRouteTracks * routeTracks
The set of edges used in this maze.
o bool costFnToRoutePts
This variable does nothing now.  I have (had) plans to make the cost function a function of how close the point is to the nearest terminal in the net, instead of the sink terminal.  This has yet to pan out and I don't think that it will give much gain in terms of quality/speed though this is just my hunch and probably the reason why I never got around to implementing it.
o static int count
Not sure what this does.

 

Constructor Index

o Maze()
Default constructor.
o Maze(int x, int y)
Initializes the maze vector to have a width of 'x' and a height of 'y'.
o Maze(int x, int y, RouteTracks *)
Initializes the maze vector to have a width of 'x' and a height of 'y'.  Sets the routeTracks to 'rt' as well as setting appropriate edges for every MazePoint in the maze vector.
o ~Maze()
The deconstructor.  Deallocates the mazePoints in the maze vector, empties and deallocates the costQ.

Method Index
 
o void putObstacle(int xValue, int yValue)
Puts an obstacel at the specified position (xValue, yValue).  An obstacle is an object in which a routing can not pass through e.g. a IP cell, a region that is already too congested, etc..
o void putSink(int xValue, int yValue)
Sets the sink to the specified position (xValue, yValue).
o void putSink(Point * sinkPt)
Sets the sink to the point 'sinkPt'.
o void putSource(int xValue, int yValue)
Sets the source point to the specified position(xValue, yValue).
o void putSource(Point * sourcePt)
Sets the source point to the point specified in 'sinkPt'.
o void setCostFnToRoutePts()
Sets the variable costFnToRoutePts which, at the present time, does absolutely nothing.
o MazePoint * getMazePointAt(int xValue, int yValue)
Returns a pointer to the maze point at the specified position (xValue, yValue).
o int valueAt(int xValue, int yValue)
Returns the "value" of the MazePoint at the specified position (xValue, yValue).  The "value" is the kind of point it is e.g. source, sink, visiited.  See MazePoint for more info.  Exactly the same as the function 'int getLength(in xValue, int yValue)'.
o int mazeRouteValueAt(int xValue, int yValue)
Returns the cost function value of the specified point (xValue, yValue).  The cost function value is used by the priority queue to choose the next point to expand.
o bool isSource(int xValue, int yValue)
Returns 'true' if the specified point has the same coordinates as the source point.
o bool isSink(int xValue, int yValue)
Returns 'true' if the specified point has the same coordinates as the sink point.
o  bool isObstacle(int xValue, int yValue)
Returns 'true' if the specified point has is set as an obstacle.
o int getLength(in xValue, int yValue)
Returns the "value" of the MazePoint at the specified position (xValue, yValue).  The "value" is the kind of point it is e.g. source, sink, visiited.  See MazePoint for more info.  Exactly the same as the function 'int valueAt(int xValue, int yValue)'.
o MazeList * getRoutePoints()
Returns the variable routePts.
o int getX()
Returns the variable x.
o int getY()
Returns the variable y.
o bool isValid(int xValue, int yValue)
Returns 'true' if the specified point is valid this maze e.g. the it is not outside of the maze.
o bool findRoute()
Function that does the actual maze routing.  The source and sink point must already be set.  This function will automatically add the routed edges to the edgeList in the Net specified by mazeNet.  The function returns 'true' if there is a route from the source to the sink.  It will return 'false' iff the sink is completely blocked from the source by obstacles.
o bool findRoute(Point * sourcePt, Point * sinkPt)
Sets the source and sink points and returns the result of the function 'bool findRoute()'.
o bool pickRoute(MazePoint *)
Internal function used by the 'findRoute()' functions.  Once the actual maze routing is completed, this function chooses the route and sets the routed edges in the Net mazeNet.
o bool pickRoute(int distance)
Internal function used by the 'findRoute()' functions.  Once the actual maze routing is completed, this function chooses the route and sets the routed edges in the Net mazeNet.
o bool routeNet(Net *)
This function takes a net, breaks it into a set of two-terminal nets and routes the two-terminal nets by maze routing i.e. calling the 'findRoute" function.  Check the PrimMST class for information on partitioning the net into two-terminal nets.
o void clearMaze()
Resets every MazePoint to its intial condition and empties the cost queue.
o void print()
Debugging function which prints the values of each MazePoint.  Mainly used to print the current state of the maze during maze routing.
o void printRouting(Net *)
Debugging function which prints the edges used while routing the mazeNet.
o void printSourceSink()
Debugging function which prints the source and sink of the maze.
o void printMazeCost()
Debugging function which prints the maze route costs of each MazePoint.  Similar to the function 'print()' except this prints the maze costs, not the value of the MazePoints.