zibbr

Random 3d and p2p stuff that was originally the beginnings of an overly ambitious p2p virtual world thingy
git clone https://code.literati.org/zibbr.git
Log | Files | Refs

readme.txt (4588B)


      1 **********************************
      2 A* Algorithm by Justin Heyes-Jones
      3 **********************************
      4 
      5 ***********
      6 Description
      7 ***********
      8 
      9 This implementation is intended to be simple to read yet fairly
     10 efficient. To build it you can compile, with any recent C++ compiler,
     11 the following files :
     12 
     13 For 8-puzzle solver
     14 
     15 	8puzzle.cpp
     16 	stlastar.h
     17 	optionally fsa.h
     18 
     19 Command line 
     20 
     21 	8puzzle with no arguments runs with one of the boards in the cpp file, you can
     22 	select the one you want changing the conditional compiliation instructions. Or if you
     23 	prefer pass in a board on the command line using digits for the tile positions, where
     24 	zero is the space. The board runs from left to right, each row at a time:
     25 	
     26 		8puzzle 013824765
     27 
     28 For path finder 
     29 
     30 	findpath.cpp
     31 	stlastar.h
     32 	optionally fsa.h
     33 
     34 	pathfind has no arguments. You can edit the simple map in pathfind.cpp and the start 
     35 	and goal co-ordinates to experiement with the pathfinder.
     36 
     37 Fixed size allocator notes: As mentioned briefly in the tutorial you can enable and disable the
     38 faster memory allocation. This allocates a fixed size block of memory, so you have to specify this size
     39 with the astar constructor. You need to enlarge it if you hit an out of memory assert during the
     40 search.
     41 
     42 Compilation notes:
     43 
     44 Microsoft Visual C++ : Confirmed working with version 8.0.50727 with some deprecation warnings
     45 I'm going to leave the deprecation warnings in so that it still works cleanly with GCC. 
     46 TODO Make a non-deprecated compliant version using compiler checking
     47 
     48 GCC notes : Compiled using version 3.4.5 (MingW)
     49 
     50 Please let me know if it doesn't work for you and I will try to help. I cannot help if you are using
     51 an old compiler such as Turbo C++, since I update the code to meet Ansi Standard C++ as required.
     52 
     53 At least in as far as the Microsoft and GCC compilers adhere to Ansi and add breaking changes.
     54 
     55 History:
     56 
     57 Updated 1th February 2009
     58 **********************************
     59 
     60 Fixed Manhattan distance bug. Should use absolute values.
     61 
     62 Got rid of sprintfs, use cout instead.
     63 
     64 Updated 3rd August 2006
     65 **********************************
     66 
     67 Fixed memory leak
     68 Fixed special case handling for finding better path to a closed node
     69 Fixed bug with comparing the start node with a new node by pointer instead of value
     70 Changed code to use Manhattan distance heuristic with pathfind.cpp as it is more correct
     71 
     72 
     73 Updated 27th September 2005
     74 **********************************
     75 
     76 Thanks to Gyan singh for pointing out the code no longer compiles under GCC.
     77 
     78 Well, that was the case. I've removed a Gnu offending conio.h include, and added lots more typename
     79 keywords, which seem to be required now when making an iterator using a template type.
     80 
     81 If anyone knows what the breaking change to the compiler was for, let me know.
     82 
     83 Updated 6th September 2005
     84 **********************************
     85 
     86 	Finally set the path to fsa.h correctly, sorry about that.
     87 	8puzzle.cpp now defaults to using a demo puzzle that solves in a short time.
     88 	Added typename keyword to comply with latest ISO standards. 
     89 
     90 Updated November 26th 2001
     91 **********************************
     92 
     93 	Fixed a bug. When a node is deleted from the Open list I did sort_heap when make_heap
     94 	is needed to keep the heap structure valid. This causes the search to go awry under some
     95 	conditions. Thanks to Mike Ryynanen for tracking this down.
     96 
     97 justinhj@hotmail.com
     98 
     99 http://www.geocities.com/jheyesjones/astar.html
    100 
    101 or
    102 
    103 http://www.heyes-jones.com/astar.html
    104 
    105 A* Algorithm Implementation using STL is
    106 Copyright (C)2001-2005 Justin Heyes-Jones
    107 
    108 Permission is given by the author to freely redistribute and 
    109 include this code in any program as long as this credit is 
    110 given where due.
    111  
    112   COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, 
    113   WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, 
    114   INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE 
    115   IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
    116   OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND 
    117   PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED 
    118   CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL 
    119   DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY 
    120   NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF 
    121   WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE 
    122   OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
    123   THIS DISCLAIMER.
    124  
    125   Use at your own risk!
    126 
    127 
    128 
    129 
    130 
    131 
    132 
    133 
    134 
    135 
    136 
    137 
    138 
    139 
    140 
    141 
    142 
    143 
    144 
    145