Polygon Game Software

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. PROBLEM DEFINITION......

3. BEFORE USING THE SOFTWARE......

3.1. Store source code files in the correct folder......

3.2. The Application Program Interface (API)......

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

3.4. Understanding the Data Structure......

3.5. Input File Format......

4. THE SOFTWARE OVERVIEW......

4.1. The JavaPolygon Working Folder......

4.2. The Application Program Interface – API.java......

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

4.4. Data Structure......

4.5. Input Format......

APPENDIX A...... 8

APPENDIX B...... 9

APPENDIX C0

APPENDIX D2

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. Return true if there is a clear path, otherwise false. / boolean / 1.Vertex A
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 xx-coordinate of this vertex

int yy-coordinate of this vertex

int PLGthe 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 Startthe start point of this Edge

Vertex Endthe 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 TotalEdgesthe numbers of total edges / vertices in this polygon

Vertex[] vListlist of all vertices in this polygon

Edge[] eListlist of all edges in this polygon

int colorthe 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:

c0Red

c1Blue

c2Green

c3Orange

c4Magenta

c5Cyan

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.

1

APPENDIX A

The Application Program Interface - API.java

APPENDIX B

Search.java

9

APPENDIX C

SearchEngine.java

9

9

APPENDIX D

Vertex.java

9

APPENDIX E

Edge.java

9

APPENDIX F

polygon.java

9