Sign in to follow this  

A* Pathfinding (Novice Programmer)

This topic is 2078 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

This topic is 2078 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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