POLYGON GAME SOFTWARE



Product Description

The “Polygon Game GUI”

Original Author: Dong Le

Ported to Java by: Maximilian Ho

Table of Contents

Page

1. INTRODUCTION 2

2. PROBLEM DEFINITION 2

3. BEFORE USING THE SOFTWARE 2

3.1. Store source code files in the correct folder 2

3.2. The Application Program Interface (API) 2

3.3. The Two Functions: returnPath() and getNumberOfPoints() 3

3.4. Understanding the Data Structure 3

3.5. Input File Format 3

4. THE SOFTWARE OVERVIEW 3

4.1. The JavaPolygon Working Folder 3

4.2. The Application Program Interface – API.java 4

4.3. Functions “returnPath” and “getNumberOfPoints” in Search.java 5

4.4. Data Structure 5

4.5. Input Format 6

APPENDIX A 8

APPENDIX B 9

APPENDIX C 10

APPENDIX D 12

APPENDIX E 13

APPENDIX F 14

1. INTRODUCTION

One of the projects in “Introduction to Artificial intelligence, ICS171” is “Polygon Game,” a project demonstrating AI search techniques taught in the course. This Software “Polygon Game GUI” is written in Java and Visual Café for the purpose of providing application tools to developers of the project. Using features in Visual Café, the software provides a basic GUI to visualize graphic on the screen, making the work easier and more fun for its users.

2. PROBLEM DEFINITION

The “Polygon Game” project in ICS171 is asking students to implement search techniques for finding paths from a start point to a goal point, through a maze consisting of non-overlapped polygons, without crossing any of the polygons. The coordinates of these start point, goal point, and points on the polygons are read from a text file.

This “Polygon Game GUI” software will provide a graphical user interface for the project. The main window with its menu allows users to open file for input and run the search algorithm to find the path. Information on the start-point, the end-point, and all the polygons read in from a file are stored in the program’s domain data structure, and displayed to the screen. At any time, the developers can query these data for their needs. When a path is found, it is also displayed on the screen, along with a statistic window showing the search time and the path’s length.

One difficult task among others in the project is to determine if there is a clear path between any pair of points in the maze. (A clear path between two points is a straight line connecting them without crossing any edge or touching any other point other than these two points themselves). However, in order to make the work easier, this software will provide a function to be used for this specific task. At any time when calling the function provided by the software, developers can check for a visible path between any two points in the maze.

3. BEFORE USING THE SOFTWARE

The following are important things a developer should know when using this product.

3.1. Store source code files in the correct folder

The software was developed using Visual Café under a project called Game.vep. The main directory for the project is called JavaPolygon. The source code to run the project is saved under the polygon directory.

3.2. The Application Program Interface (API)

The software provides an API to its users in the file API.java. This package provides an interface which allows several function calls, including querying data on the start point, the goal point, and the polygons in the maze. It is through this package that developers can make calls to the function isVisibility() to check for a clear path between any two points in the maze. For a detailed description of the API, please refer to section 4.2.

3.3. The Two Functions: returnPath() and getNumberOfPoints()

When the search option from the menu is selected, the software will invoke two functions called returnPath and getNumberOfPoints. The prototypes of those two functions are defined in the file Search.java. In order for the program to work, developers must create a subclass of the class Search and write the code for these two functions. Search.java is stored under the JavaPolygon folder. For details on the requirements of returnPath and getNumberOfPoints, please refer to section 4.3.

3.4. Understanding the Data Structure

It is important to understand the Data Structure used in the software. Developers need to understand the data structure of the class Vertex in order to write the function returnPath. In addition, developers might also want to understand the data structures of the class Edge and the class polygon. For details on data structures, please refer to section 4.4.

3.5. Input File Format

All input files to be read by the program must be in a correct format. A correct input file will include xy-coordinates for a start point, a goal point, and points for polygons if there is any of them. For a detailed description of the input file format, please refer to section 4.5.

4. THE SOFTWARE OVERVIEW

This section describes the Working Folder and the Work Space, the Application Program Interface, the two functions returnPath() and getNumberOfPoints(), the Data Structure, and the Input Format of the JavaPolygon Project.

4.1. The JavaPolygon Working Folder

All source codes and related files to the program are stored in the folder JavaPolygon. The Polygon folder also contains a sub folder called TestFiles where developers can find several examples of input-files for testing the program. Figure 1 on next page shows a picture of the folder JavaPolygon.

Figure 1. JavaPolygon folder

4.2. The Application Program Interface – API.java

The API provides seven functions as follow:

(1) boolean isVisible()

(2) Vertex getStart()

(3) Vertex getGoal()

(4) int getNumberOfVertices()

(5) Vertex[] getVertexArray()

(6) int getNumberOfPolygons()

7) polygon[] getPolygonArray()

Each of the functions is described in following table:

|Function name |Description |Return Type |Parameters |

|isVisible |Check for a clear path between vertex A and vertex B. |boolean |1.Vertex A |

| |Return true if there is a clear path, otherwise false. | |2.Vertex B |

|getStart |Return the start vertex in the maze. |Vertex |None |

|getGoal |Return the goal vertex in the maze. |Vertex |None |

|getNumberOfVertices |Return the numbers of all vertices in the maze. |int |None |

|getVertexArray |Return the array holding all vertices in the maze. |Vertex[] |None |

|getNumberOfPolygons |Return the numbers of all polygons in the maze. |int |None |

|getPolygonArray |Return the array holding all polygons in the maze. |polygon[] |None |

The implementation of this API in Java is enclosed in appendix A.

4.3. Functions “returnPath” and “getNumberOfPoints” in Search.java

The file Search.java under the JavaPolygon folder has two important functions to be described as follow:

1) returnPath:

Syntax: Vertex[] returnPath();

Description: This function will return the array holding vertices of the path form start to goal in the maze. For the testing purpose, developers will find this function is currently returning a dummy path consisting of five vertices. The program will use this information to draw the path on the screen. Developers need to modify this function in order to make it return a correct path.

2) getNumberOfPoints:

Syntax: int getNumberOfPoints();

Description: This function will return the numbers of total vertices in the path. For the testing purposes, developers will find this function is currently returning the value five. The program needs this information to draw the path on the screen. Developers need to modify this function in order to make it return a correct number.

The file Search.java is enclosed in appendix B.

4.4. Data Structure

The main four data structures, used in the program to store information on the start point, the goal point and the polygons in the maze, are:

3) class Vertex

Object instantiated from this class will have these properties:

int x x-coordinate of this vertex

int y y-coordinate of this vertex

int PLG the number indicates what polygon this vertex belongs to. This number equals zero if this vertex is either the start point or the goal point.

The declaration of this class in Java is enclosed in appendix D.

4) class Edge

Object instantiated from this class will have these properties:

Vertex Start the start point of this Edge

Vertex End the end point of this Edge

The declaration of this class in Java is enclosed in appendix E.

5) class polygon

Object instantiated from this class will have these properties:

int TotalEdges the numbers of total edges / vertices in this polygon

Vertex[] vList list of all vertices in this polygon

Edge[] eList list of all edges in this polygon

int color the color of this polygon being displayed on the screen, where 0=Red, 1=Blue, 2=Green, 3=Orange, 4=Magenta, 5= Cyan, and others=Gray.

The declaration of this class in Java is enclosed in appendix F.

4.5. Input Format

A point in the plane presented by its x- and y-coordinators enclosed in parentheses.

Example: (25, 40) presents the point with x-coordinate 25 and y-coordinate 40.

A polygon in the plane presented by a series of all points in it following the counter-clockwise order. A polygon is terminated by a color code as shown below:

c0 Red

c1 Blue

c2 Green

c3 Orange

c4 Magenta

c5 Cyan

Any number other than the above means the color is gray, e.g. c12 = color is gray.

Example: (12,8) (24,8) (24,11) (12,11) c1 present a blue polygon with 4 points.

All input files to the program will have the following format:

Start with the start point in the format described above.

The goal point may stay on the same line or on the next line.

All polygons must end with a color code as described above.

Note: If there is at least one polygon in the maze, the file must contain a start point and a goal point.

Input file example:

The following input file will make the screen display shown in figure 2:

(36,4) (19,19)

(5,7) (13,4) (7,16) c0

(12,8) (24,8) (24,11) (12,11) c1

(26,5) (35,13) (26,11) c4

(21,13) (32,13) (32,21) (21,21) c2

(9,15) (18,15) (18,21) (9,21) c3

(5,12) (5,25) (0,15) c4

(8,22) (15,30) (5,28) c5

(15,23) (23,23) (23,28) (15,28) c3

(37,17) (36,27) (23,30) c6

Figure 2. The screen display after the program read the above input file

More examples on input files can be found in the sub folder “TestFiles” inside the “JavaPolygon” folder.

APPENDIX A

The Application Program Interface - API.java

APPENDIX B

Search.java

APPENDIX C

SearchEngine.java

APPENDIX D

Vertex.java

APPENDIX E

Edge.java

APPENDIX F

polygon.java

-----------------------

///////////////////// THE APPLICATION PROGRAM INTERFACE /////////////////////

public class API

{

//Returns true if there is a clear path between the two vertices v1 & v2

public static boolean isVisible(final Vertex v1, final Vertex v2)

{

return theMaze.isVisible(v1, v2);

}

//Returns the start vertex. User should make a copy

//if he/she wants to modify it.

public static Vertex getStart()

{

return theMaze.getStart();

}

//Returns the goal vertex. User should make a copy

//if he/she wants to modify it.

public static Vertex getGoal()

{

return theMaze.getGoal();

}

// Returns the total number of vertices in the maze.

public static int getNumberOfVertices()

{

return theMaze.getNumberOfVertices();

}

//Returns a dynamic array holding all vertices in the maze.

//User should make a copy if he/she wants to modify it.

public static Vertex[] getVertexArray()

{

return theMaze.getVertexArray();

}

//Returns the total number of polygons in the maze.

public static int getNumberOfPolygons()

{

return theMaze.getNumberOfPolygons();

}

// Returns a dynamic the array holding all polygons in the maze.

//User should make a copy if he/she wants to modify it.

public static polygon[] getPolygonArray()

{

return theMaze.getPolygonArray();

}

/////////For internal use only/////////////

//////////Do not call these!////////////////

public static void resetMaze()

{

API.theMaze = null;

}

public static void setMaze(Maze theMaze) {API.theMaze = theMaze;}

///////////////////////////////////////////

private static Maze theMaze = null;

}

public class SearchEngine

{

public SearchEngine()

{

//Plug search Classes into here

searchAStar = null;//new AStar();

searchBFS = new BFS();

searchDFS = null;//new DFS();

}

public Vertex[] returnPath()

{

if(selectedAlg != null)

return selectedAlg.returnPath();

else

return null;

}

public int getNumberOfPoints()

{

if(selectedAlg != null)

return selectedAlg.getNumberOfPoints();

else

return 0;

}

public void setAlgorithm(final int algorithm)

{

switch(algorithm)

{

case AStarAlg:

selectedAlg = searchAStar;

break;

case BFSAlg:

selectedAlg = searchBFS;

break;

case DFSAlg:

selectedAlg = searchDFS;

break;

default:

selectedAlg = null;

break;

}

}

/*----------------------------------------------------------------------------------------------------------||

|| Class Vertex ||

||-----------------------------------------------------------------------------------------------------------||

|| Member Data - Access through member funtions only: ||

|| int x x-coordinate ||

|| int y y-coordinate ||

|| int PLG the polygon# this vertex belongs to ||

|| ||

|| Methods provide: ||

|| Vertex(int a, int b, int p) Assign constructor ||

|| Vertex(final Vertex v) Copy constructor ||

|| getX() Access x-coordinate ||

|| getY() Access y-coordinate ||

|| getPLG() Access the polygon# ||

|| setX(int n) Change x-coordinate ||

|| setY(int n) Change y-coordinate ||

|| setPLG(int n) Change polygon# ||

|| Vertex setEqual(final Vertex rhs) Sets one Vertex equal to another ||

|| boolean equals(Object obj) Returns true if both Vertices are equal ||

|| ||

||-----------------------------------------------------------------------------------------------------------||

||----------------------------------------------------------------------------------------------------------*/

import java.awt.*;

public class polygon implements Cloneable

{

public polygon()

{

TotalEdges = 0;

vList = null;

eList = null;

color = 6;

}

public polygon(Vertex array[], int n, int color)

{

TotalEdges = n;

this.color = color;

vList = new Vertex[n];

eList = new Edge[n];

for( int i = 0; i < n; i++ )

{

vList[i] = new Vertex(array[i]);

if( i > 0 )

eList[i-1] = new Edge(vList[i-1],vList[i]);

}

eList[n-1] = new Edge(vList[n-1],vList[0]);

}

public polygon(final polygon p)

{

TotalEdges = p.TotalEdges;

this.color = p.color;

vList = new Vertex[TotalEdges];

eList = new Edge[TotalEdges];

for( int i = 0; i < TotalEdges; i++ )

{

vList[i] = new Vertex(p.vList[i]);

eList[i] = new Edge(p.eList[i]);

}

}

public Object clone() throws CloneNotSupportedException

{

return super.clone();

}

public polygon setEqual(final polygon rhs)

{

TotalEdges = rhs.TotalEdges;

this.color = rhs.color;

vList = new Vertex[TotalEdges];

eList = new Edge[TotalEdges];

for( int i = 0; i < TotalEdges; i++ )

{

vList[i] = new Vertex(rhs.vList[i]);

eList[i] = new Edge(rhs.eList[i]);

}

return this; //enable chainning of type v1 = v2 = v3

}

public int TotalEdges;

public Vertex []vList; // List of all nodes in the polygon

public Edge []eList; // List of all edges in the polygon

public int color;

}

/*----------------------------------------------------------------------------------------------------------||

||Class Edge ||

||-----------------------------------------------------------------------------------------------------------||

|| Member Data - Access through member funtions only: ||

|| Vertex Start Start point of the edge ||

|| Vertex End End point of the edge ||

|| ||

|| Methods Provide: ||

|| Edge(); Default constructor ||

|| Edge(final Vertex a, final Vertex b) Assign constructor ||

|| ||

|| getStart() Access start point ||

|| getEnd() Access end point ||

|| getMidPoint() Get midpoint of the edge ||

|| getReverse() Get the reverse edge ||

|| getLength() Get the edge's length ||

|| setStart(final Vertex v) Change start point ||

|| setStart(int x, int y, int p) Change start point ||

|| setEnd(final Vertex v) Change end point ||

|| setEnd(int x, int y, int p) Change end point ||

|| isIntersect(final Edge PQ, int skew) Does the pass-in edge cross this edge? ||

|| Edge setEqual(final Edge rhs) Sets one edge equal to another ||

|| boolean equals(Object obj) Returns true if both edges are equal ||

|| ||

||-----------------------------------------------------------------------------------------------------------||

||---------------------------------------------------------------------------------------------------------*/

public abstract class Search

{

public Search() {}

public abstract Vertex[] returnPath();

public abstract int getNumberOfPoints();

}

Goal

[pic]

[pic]

[pic]

public boolean isEnabled(final int algorithm)

{

switch(algorithm)

{

case AStarAlg:

if(searchAStar != null)

return true;

break;

case BFSAlg:

if(searchBFS != null)

return true;

break;

case DFSAlg:

if(searchDFS != null)

return true;

break;

}

return false;

}

private Search searchAStar = null;

private Search searchDFS = null;

private Search searchBFS = null;

private Search selectedAlg = null;

public final static int BFSAlg = 0;

public final static int DFSAlg = 1;

public final static int AStarAlg = 2;

}

Start

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download