Java代写:COMS228 Explore Documentation

代写一个算法作业,对模拟的六边形地形,实现搜索算法寻找最短路径。

User manual

Explore constructs hex-grid terrain maps from a textual specification and produces a graphical display of the result (Error: Reference source not found.) Version 2 adds a new shortest path capability.

Explore v.2 can draw any size rectangular map your computer hardware can accommodate. The display engine will automatically supply scroll bars for maps which are too big for your display.

Explore v.2 maps are composed of terrain cells and cell to cell “connectors” which describe traffic way and water ways. Connectors are “weighted” by their traffic capacity. Version 2 also includes provision for marking start and end cells and for computing the shortest path between those cells. The viewer includes new support for displaying the shortest path. (See Error: Reference source not found.)

Explore Terrain Features

Terrain maps are composed of up to four different terrain types, four different connector types, barriers, and some special markers. Each cell’s “background” graphic corresponds to the terrain type in that cell. details the different terrain types. Traffic can cross from cell to cell, even without a connector. When there is no connector at a cell edge, the traffic capacity is that of the lower capacity cell.

Connectors cross cell boundaries, going from center to center on adjacent cells. Each Connector has a traffic capacity independent of the underlying terrain. Error: Reference source not found gives connector details. Traffic capacity goes up as edge weight (cost of travel) goes down.

Explore automatically computes the effective capacity of each cell wall, using the following policy:

  • if the has a barrier, the weight for that edge is 900.
  • if the there is no connector between two cells, the weight is the maximum of the terrain weight in the two cells. For example, an edge between forest and default would have an effective weight of 195.
  • if there is a connector between two cells the edge weight will be the connecter weight. (It is possible for the edge weight to be less than the connector weight, but only if the capacity of the underlying terrain exceeded the capacity of the connector.
    Table 1 - Terrain details
Name Represents Weight
default Relatively flat, easily traversed open land. 165
brush Like default, but with low obstacles. 180
forest Dense trees. Difficult for vehicular traffic. 195
water Open, relatively still water, such as a lake or pond. Not necessarily suitable for high speed craft. 190
flag1 The start cell. 0
flag2 The finish point. 0

Table 2 - Connector Details

Names Represents Weight
dividedhwy, Hw4 An interstate or turnpike quality high speed trafficway. 110
hwy, Hw2 A two-lane, two-way (e.g., state or county) highway. 130
unpaved, dirt An unpaved, dirt or gravel road or path 143
river Moving water, but may be navigable only by certain craft. 185
barrierwall, wall A barrier. 900

Installation

Explore is supplied only as source code. Thus, there is no installer. Explore is distributed as a single zip archive file. The name of this file may differ between providers and versions. If you cannot determine the appropriate file to download, please contact your provider.

If you are a developer, you may prefer to follow the installation advice in the Developer Documentation and add the source to a project in your IDE.

To install the application as a user:

  1. Download the zip file into a folder (directory) of your choice.
  2. Use your local system zip utility to unpack the file. Depending on your operating, this utility may be named unzip, gunzip, zip, 7-zip, or something similar. On many systems you can simply right click on the file in your file browser and select “unzip” or “extract here”.
  3. Once you have unpacked the archive, you should browse into the new file hierarchy. In the first two or three levels you should find a folder named “src”.
  4. When you have found this “src” directory, open a command line shell and cd into the src directory. (If this operation is unfamiliar, ask a developer friend for help.
  5. You now need to compile the code.
  6. If the compile operation completes without any messages indicating an error, then you should now have an executable version of Explore.

Creating Your Own Terrain Files

Explore terrain descriptions are simple text files. Thus you can create your own mazes in any simple text editor. (Explore graph descriptions must be .txt files. Explore does not understand word processer or document files, such as .doc or .pdf.)

Locations

Locations in the terrain file are specified with Hex coordinates, corresponding to a vertical column number and a diagonal row number, as highlighted in Error: Reference source not found. Note that cell(0,0) is at the upper left corner, and rows and columns indexes grow larger as you move right and down. The left number in cell(x,y) corresponds to the cell’s column; the right number to its diagonal row. The red star in Error: Reference source not found is in cell(1,2).

(Tip: You can make a screen capture of a terrain map with no features, and print it to create a nicely labeled design layout grid. Creating the text file is much easier if you draw your terrain design on the grid and then transcribe the cell appropriate cell numbers.)

Directions

Cell walls are named by their direction from the center of the cell. In terrain files, these wall names (in clockwise order from the top of the cell) are abbreviated “up”, “ur”, “dr”, “dn” “dl”, and “ul”.

Case is important! While Explore will ignore case in some instances, it is best practice to use only lower case characters in a terrain description file.

File Structure

A legal Explore terrain description consists of a geometry section (which defines the dimensions of the map) followed by sections that describe terrain, connectors, and flag locations. With the exception of the geometry section (which must appear only once, and must be first in the file) and the flag section (which may appear only once in a file), map description sections may be listed in any order and may be repeated (with different location information) as many times as you need.

Error: Reference source not found shows an example terrain description file which includes an instance of all available features and connectors.

With the exception of the geometry and barrierwall section (detailed later), each of the terrain description sections are structured as a keyword (like “water” or “river”) followed by a list of hex coordinates.

Terrain Coordinates

For terrain keywords, the list of coordinates represents individual cells of the same terrain. Thus, the list can be one or more coordinates and they can be contiguous, isolated, or broken into several clusters. Some designers find it useful to define each cluster of like terrain in a different section. Explore doesn’t care.

Connector Paths

The coordinates supplied with a connector, though, must meet constraints that assure they describe a continuous path through the centers of adjacent cells. Thus the coordinate list accompanying each connector keyword (a river, for example) must include at least two coordinates, and the coordinates must, in order, pass through centers of adjacent cells.

Flag Coordinates

The flag keyword must be followed by exactly two coordinates: one for the blue start flag and one for the red goal (or end) flag.

Geometry

The geometry keyword must be followed by exactly two integers. The first represents the number of columns in the board; the second the number of horizontal (not hex diagonal) rows. The resulting board is always rectangular.

Barrier Walls

Barrier walls are described in short sections (called border segments), where each section consists of all the cell walls (by direction) in a particular cell (by coordinate) that are blocked by a barrier. For example, the following border segment describes two full barriers in Error: Reference source not found:

2 4 up ur

Each such border segment consists of a coordinate pair followed by a list of cell walls, named by direction.

A barrierwall keyword can be followed by as many border segment descriptions as convenient. Some designers like to describe each connected run of barrier in a separate barrierwall section.

Displaying A Terrain Map

To display a particular terrain map, you should use the same command you used to display the demonstration map, but follow “…/Explore” with the path to your terrain file. If you moved Explore.java to your working directory and recompiled there (as suggested at the end of the installation instructions), then you should be able to display any description file located in your working directory by entering the command

Explore <terrain file name>

You can also use a relative path or an absolute path in place of the simple filename. For example if you have created a “terrains” directory in your Explore working directory, then you could load a file (say “myTerrain.txt”) from the terrains directory with

Explore terrains/myTerrain.txt

If neither of these options is convenient for you, there are other installation options that might be. Contact the dissussion board or a developer friend for details.

If You Need Help

Check our discussion board. Other users have probably encountered similar problems, so there is a good chance you will find the answer there. If you don’t find an answer to your question, you can always pose a new question on the discussion board.

If you need additional support, please contact the provider from whom you acquired the zip.

Developer Notes

Overview, Design, and Architecture

Figure 1 shows the key inheritance and uses relationships in Explore. While there are many small classes that encapsulate certain key relationships or act as data transfer objects, the classes in this drawing are the application’s primary actors.

Terrain File Syntax

The augmented grammar of the file is

<file>:: geometry <pair> <feature>+
<feature>:: <flags>?|<terrain>*|<connector>*| <barrier>*
<flags>:: <coord><coord>
<terrain> :: (water|brush|forest) <coord>+ 
<connector>::(hwy|dividedhwy|unpaved|river) <path>
<path> :: <start coord><adj coord>*<end coord>
<barrier>:: barrierwall <border segment>+
<border segment> :: <coord> <dir list>

Additional information

  • The file must start with a geometry section, so that the Coordinate geometry can be set before processing any terrain features.
  • Geometry and flags may only appear once. Geometry is required. The flags section is optional. If it is not present, you should not attempt to run your solver.
  • The cells listed in terrain sections do not need to be contiguous. However it might make it easier for you to check the file against your terrain plan if you use a separate section for each contiguous region. Two regions of forest would be described in two different “forest” sections.
  • Each connector section must list at least two coordinates (a start and an end). Each pair of connectors in a section list must correspond to adjacent cells. Thus each continuous run of highway, for example, should be described in its own section and the coordinates should name the cells in the order they are crossed. Unconnected (and crossing) highways should each have their own section. The same path-related restrictions apply to all connector types except barrierwall.

Identified Technical Debt

  • Class Delta.
  • Resource handling.
  • Default Terrain directory
  • Self-painting cells, connectors, and other graphic components.
  • Independent JPanels for each drawing layer.
  • Logging system
  • Automated Tests
  • Subclassing Graph.Edge and Graph.Vertex (vs. edge data lookup)
  • Richer Path Component
  • Pattern fragility in NoiseFilterReader
  • Open instead of packaged library
  • The viewer should have a diagnostic mode which displays linear index and effective edge weights on each vertex.

Version and Other History Notes

Unlike Maze, the 2.0 version of Explore is currently broken. We believe that, given an appropriate implementation of PathFinder, the new shortest path feature should “just work.” All of the display functionality and related wiring is there and has been tested separately.

However, a rewrite of the main parsing code in TerrainLoader has not been finished. Several important helper and data transfer classes have been completed and tested, but the code which uses these to invoke the construction methods in TerrainGraph has not been written. See the details elsewhere in the developer notes.

Coding Status in TerrainLoader

All of the work related to finding the terrain file, opening it, and connecting the appropriate chain of readers is completed, mostly outside of TerrainLoader. Within TerrainLoader, the initial parsing of sections (identifying each type of section by its lead keyword) is complete. Additionally, both the parsing and the proper configuration of Coordinate/graph Geometry is complete.

The unfinished portions of TerrainLoader all involve parsing coordinates, paths, and border segments. There is special support in for recognizing these structures in the new TerrainScanner (which is described elsewhere in these notes). Use it.

Incomplete methods are marked with //TODO: The following wiring diagram shows how the incomplete methods should connect (use) TerrainGraph. . Most of these methods readXXX where “XXX” is some structure (like a path or border segment) in the description file. Each read method constructs an appropriate set of data transfer objects and “pushes” them to the relevant construction method in TerrainGraph, listed below:

  • setFlags(Coordinate flag1, Coordinate flag2). Records the cells selected for the start and end points, respectively, of the shortest path search function. Attempts to select the same cell for both flags should result in a parse error with appropriate diagnostic message.

  • setConnectedPath(Path path, ConnType type). Lays down a connected section of highway, or other connector.

  • setTerrain(List coords, TerrainType type). Marks the cells listed in coords as being type terrain. Used for water, forrest, and brush. Note that default terrain is never marked nor indicated explicitly in the terrain description.

  • setBorderEdges(List, ConnType). Updates the many graph edges and weights involved in a setting up a continuous chain of barriers. Presently this method is used only for barrierwall, but it is designed to be general enough to support other types of cell perimeter attributes. Thus, the parsing code should not hard-wire the connector type.

  • SetSolution(Path). Normally, terrain files will not include this element This section is supported only to enable us to test the display engine’s support for the new shortest path feature independently of the shortest path computation. The path specified to this call is not incorporated into the main graph structure, so it has no effect on edge weights. Furthermore, the display engine will image this element on a layer above the normal connectors, so they will not be lost. Any attempt to use the same Coordinate for start and end should result in a Parse Error with appropriate diagnostic information.

The following “wiring diagram” shows how the parsing routines in TerrainLoader connect to graph operations in TerrainGraph.

Developer Infrastructure

Drivers and Automated tests

TestLoader is designed to make it easier to test and develop the parsing code in TerrainLoader. Using it, you can easily test specifications with just one type of section, or specific combinations of sections without needing to deal with data files and command-line invocation. While it has been used as a driver to date, it should be fairly easy to construct automated verification for specific small tests.

DTOs and Domain Abstractions

Some of the most important “developer infrastructure” in this project consists of the collection of data transfer objects and small abstractions we’ve developed to simplify operations and improve the expressibility of concepts in the hex grid space.

Coordinate, Coordinate.Pair, Path, BorderSegment, ConnType, and TerrainType.

Some of these classes are described in more detail here, but even if the class is not described here, you should take time to find the definition and familiarize yourself with its API. You wil need to use virtually all of these objects if you parse a terrain description.

Class Coordinate

Because of the need for convenient interactions among the underlying, linear Graph object, the rectangular coordinate display system, and the hex board components, convenient and reliable coordinate translation is a must. Thus we have encapsulated almost all knowledge of coordinate systems and “world geometry” in the Coordinate class. We have also encapsulated information about grid directions in a complex HexDir enum.

Class Coordinate represents both the “identity” of the cell and its associated vertex, and knows how to produce, on demand, the right corresponding identity value in any of the coordinate.

A Coordinate object can be constructed from any of the graph coordinate values.

  • Coordinate(int i) constructs a coordinate starting from a vertex’s linear index.
  • Coordinate(int xHex, int yHex) starts from a hex coordinate pair.
  • Coordinate( int x , int y, boolean true) starts from a rectangular x,y pair.

Once created, a Coordinate instance can produce a convenient to use value in any of the systems. Single-valued (linear) coordinates are ints. Two-valued coordinates are returned as a Pair object which includes an external flag (‘B’, ‘R’, ‘S’) indicating whether it belongs to the Board (hex), Rectangular, or Screen coordinate system.

  • public Pair getBoard() returns a hex pair,
  • public Pair getRect () returns a rectangular pair, and
  • public int getLinear() returns the linear value.

Coordinate objects also support various utility and convenience functions. For example:

  • Boolean isValid(Pair coord) will tell you if the coordinate is within the grid or its graph.
  • Pair getDelta( Coordinate c) computes the hex-valued difference between two coordinates.
  • Coordinate get(HexDir dir) returns the coordinate of the board neighbor at direction dir.

Several functions test whether or not Coordinates and Pairs represent neighbors.

HexDir

In Explore, edges between vertices correspond to directions on the board, so it is convenient to have a way to identify, represent, and manipulate these directions. The complex enum HexDir (complex because it supports many mapping and characterization functions) is an important companion to Pair and Coordinate. HexDir not only gives you convenient direction names and convenient iteration through directions, it also knows how to convert Pair instances (e.g., delta’s between two Coordinates) into conveniently tested HexDir values. Of particular use in this project:

  • HexDir reverse() returns the HexDir for 180 degrees from this direction.
  • HexDir fromAbbrev(String d) returns the HexDir corresponding to the two letter border segment direction abbreviation (see the discussion of BorderSegments in the section on Explore’s file format.

TerrainScanner

A specialized scanner, TerrainScanner, knows how to recognize not just Java types, but also Coordinates, direction abbreviations, and BorderSegments. Thus, once you have recognized the dividedhwy keyword, you can just loop over the coordinate elements like this.

The same strategy works for the more complex BorderSegment elements.

TerrainScanner will not work reliably unless the input stream has been pre-processed by NoiseFilterReader.

NoiseFilterReader

NoiseFilterReader which will replace all punctuation (noise or eye candy) and linefeeds with space characters. You must use this reader if you want to use Terrain Scanner. More importantly, though, this allows you to use whatever punctuation you find helpful when authoring a terrain description file. All of that noise, while it certainly helps readability, can greatly complicate parsing. The NoiseFilterReader makes it all go away.

To process a string (e.g., to make test construction more convenient), the setup would be.

A similar sequence, but chaining File and FileReader in place of StringReader can be used to strip punctuation from your terrain descriptions.

The NoiseFilterReader is an example of specialization through delegation (instead of through inheritance). If you look at the definition, you will see a lot of code, but with the exception of three or four methods, all of that code was generated using the eclipse source>generate>delegate.

Diagnostic Aids

The toString() override on Graph (inherited by both HexGraph and TerrainGraph) will print the following style dump of the graph with edge weights. If called after TerrainLoader has finished constructing TerrainGraph, you will get a dump like the following, which includes the effective weight associated with each vertex. Currently this is the most convenient way to check that edge weights are being computed properly.