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