Skip to content

Commit 3816a6b

Browse files
justinhjjustinhj
committed
Merge branch 'master' of github.com:justinhj/astar-algorithm-cpp
2 parents 7b484bf + b25dd66 commit 3816a6b

7 files changed

Lines changed: 733 additions & 75 deletions

File tree

‎README.md‎

Lines changed: 10 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,11 @@ astar-algorithm-cpp
44
Summary
55
-------
66

7-
This code is an efficient implementation in C++ of the A* algorithm. It accompanies the A* tutorial on this site: http://www.heyes-jones.com/astar.html
7+
This code is an efficient implementation in C++ and C# of the A* algorithm. It accompanies the A* tutorial on this site: http://www.heyes-jones.com/astar.html
88

9-
The code has been used in several popular video games including THQ's "Company of Heroes", Activision's "Gun" as well as in the popular game prototyping engine Angel. http://code.google.com/p/angel-engine/
9+
Thank you @ScaryG for the C# port. This should work on Unity as well as the .net or mono platforms.
10+
11+
The CPP code has been used in several popular video games including THQ's "Company of Heroes", Activision's "Gun" as well as in the popular game prototyping engine Angel. http://code.google.com/p/angel-engine/
1012

1113
It has also used in many University assignments and projects.
1214

@@ -28,10 +30,10 @@ Using this code:
2830
* Company of Heroes and Company of Heroes Online, Relic Entertainment
2931
* Angel Engine, a game prototyping engine http://code.google.com/p/angel-engine/
3032

31-
Installing
32-
==========
33+
Compilation
34+
===========
3335

34-
Build in place using:
36+
Build via GCC like so:
3537

3638
g++ findpath.cpp -o findpath
3739

@@ -79,68 +81,12 @@ Microsoft Visual C++ : Confirmed working with version 8.0.50727 with some deprec
7981
I'm going to leave the deprecation warnings in so that it still works cleanly with GCC.
8082
TODO Make a non-deprecated compliant version using compiler checking
8183

82-
GCC notes : Compiled using version 3.4.4
84+
GCC notes : Compiled using version 4.2.1
8385

8486
Please let me know if it doesn't work for you and I will try to help. I cannot help if you are using
8587
an old compiler such as Turbo C++, since I update the code to meet Ansi Standard C++ as required.
86-
87-
At least in as far as the Microsoft and GCC compilers adhere to Ansi and add breaking changes.
88-
89-
History:
90-
91-
Updated 3rd August 2006
92-
-----------------------
93-
94-
Fixed memory leak
95-
Fixed special case handling for finding better path to a closed node
96-
Fixed bug with comparing the start node with a new node by pointer instead of value
97-
Changed code to use Manhattan distance heuristic with pathfind.cpp as it is more correct
98-
99-
100-
Updated 27th September 2005
101-
---------------------------
102-
103-
Thanks to Gyan singh for pointing out the code no longer compiles under GCC.
104-
105-
Well, that was the case. I've removed a Gnu offending conio.h include, and added lots more typename
106-
keywords, which seem to be required now when making an iterator using a template type.
107-
108-
If anyone knows what the breaking change to the compiler was for, let me know.
109-
110-
Updated 6th September 2005
111-
--------------------------
112-
113-
Finally set the path to fsa.h correctly, sorry about that.
114-
8puzzle.cpp now defaults to using a demo puzzle that solves in a short time.
115-
Added typename keyword to comply with latest ISO standards.
116-
117-
Updated November 26th 2001
118-
--------------------------
119-
120-
Fixed a bug. When a node is deleted from the Open list I did sort_heap when make_heap
121-
is needed to keep the heap structure valid. This causes the search to go awry under some
122-
conditions. Thanks to Mike Ryynanen for tracking this down.
123-
124-
125-
126-
127-
128-
129-
130-
131-
132-
133-
134-
135-
136-
137-
138-
139-
140-
141-
142-
143-
14488

14589

90+
Cheers!
14691

92+
Justin

8puzzle.cpp renamed to cpp/8puzzle.cpp

File renamed without changes.

findpath.cpp renamed to cpp/findpath.cpp

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -76,11 +76,11 @@ int GetMap( int x, int y )
7676
class MapSearchNode
7777
{
7878
public:
79-
unsigned int x; // the (x,y) positions of the node
80-
unsigned int y;
79+
int x; // the (x,y) positions of the node
80+
int y;
8181

8282
MapSearchNode() { x = y = 0; }
83-
MapSearchNode( unsigned int px, unsigned int py ) { x=px; y=py; }
83+
MapSearchNode( int px, int py ) { x=px; y=py; }
8484

8585
float GoalDistanceEstimate( MapSearchNode &nodeGoal );
8686
bool IsGoal( MapSearchNode &nodeGoal );

fsa.h renamed to cpp/fsa.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -71,8 +71,8 @@ template <class USER_TYPE> class FixedSizeAllocator
7171

7272
public: // methods
7373
FixedSizeAllocator( unsigned int MaxElements = FSA_DEFAULT_SIZE ) :
74-
m_MaxElements( MaxElements ),
75-
m_pFirstUsed( NULL )
74+
m_pFirstUsed( NULL ),
75+
m_MaxElements( MaxElements )
7676
{
7777
// Allocate enough memory for the maximum number of elements
7878

stlastar.h renamed to cpp/stlastar.h

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,9 @@ using namespace std;
4848

4949
// disable warning that debugging information has lines that are truncated
5050
// occurs in stl headers
51+
#if defined(WIN32) && defined(_WINDOWS)
5152
#pragma warning( disable : 4786 )
53+
#endif
5254

5355
template <class T> class AStarState;
5456

@@ -117,23 +119,23 @@ template <class UserState> class AStarSearch
117119

118120
// constructor just initialises private data
119121
AStarSearch() :
120-
m_AllocateNodeCount(0),
122+
m_State( SEARCH_STATE_NOT_INITIALISED ),
123+
m_CurrentSolutionNode( NULL ),
121124
#if USE_FSA_MEMORY
122125
m_FixedSizeAllocator( 1000 ),
123126
#endif
124-
m_State( SEARCH_STATE_NOT_INITIALISED ),
125-
m_CurrentSolutionNode( NULL ),
127+
m_AllocateNodeCount(0),
126128
m_CancelRequest( false )
127129
{
128130
}
129131

130132
AStarSearch( int MaxNodes ) :
131-
m_AllocateNodeCount(0),
133+
m_State( SEARCH_STATE_NOT_INITIALISED ),
134+
m_CurrentSolutionNode( NULL ),
132135
#if USE_FSA_MEMORY
133136
m_FixedSizeAllocator( MaxNodes ),
134137
#endif
135-
m_State( SEARCH_STATE_NOT_INITIALISED ),
136-
m_CurrentSolutionNode( NULL ),
138+
m_AllocateNodeCount(0),
137139
m_CancelRequest( false )
138140
{
139141
}

0 commit comments

Comments
 (0)