Sign in to follow this  
RedShft

A* Pathfinding (Novice Programmer)

Recommended Posts

**Edit**: I've decided to go through "Programming Game AI by Example" by Buckland and revisit this problem later

Hello Everyone,
This is my first time posting on this site, so I hope I haven't messed anything up yet. With that being said, I'm a novice programmer just getting into AI. I'm working on a game right now in SDL and the D programming language. My game is a basic 2D shooter, that uses tiled as the map editor. I'm at the point where I'm trying to implement A* in my game. I've looked at several online tutorials, and explanations and I've also been following Millington's book "Artificial Intelligence for Game". While I feel I have a decent grasp of the theory behind A*, I'm having trouble converting this to working code.

My basic approach I am taking is trying to implement his Node Array A* method. I'm using a struct to represent my nodes, with position (index on the map and pixels), parent, scores and it's category. I decided to use category which represents what list the node is on and the possible values are open, closed or uninvited. When a node is determined to be unvisited, I create a reference, which holds the nodes array index on the PathGraph and the f score which is then stored on the openlist.

My open list is implemented as a simple min heap, in the regular fashion with the lowest f score at the front.

The problem I have is this:

The way I've found to implement a min heap in D is that it must have a max capacity and cannot be grown above a certain length. I wouldn't think this would be a problem if I set the max capacity to the maximum amount of nodes on my map as the length of the actual min heap should stay below that. However, when I fire up my game, and test it, my game crashes because the open lists length gets to a point where it tries to grow, which then throws an exception and the game crashes.

What's alarming is that if I set the capacity of my min heap to 5000, it will get to that point and crash. Which means that I have duplicate entrires on my open list. I don't entire understand how because every node on the path graph should be visited and marked as closed.

Specifically it says " Exception: Cannot Grow Heap over a range ".

Any help would be appreciated. I hope this is the appropriate place to post this question. If not just let me know and I'll fix this.

[url="http://codepad.org/QS26mwMD"]http://codepad.org/QS26mwMD[/url]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this