Maze Solver - A-Star Path Finding

[Randall]

Hello All,

I've been pretty quiet lately because I've been busy learning thinBasic and how to develop a module. I now have something to show, as my first attempt. I will welcome your criticism of it, as I will learn from what you have to say. Perhaps others will learn from your comments as well.

This is a very simple application. You draw a maze on the screen, pick starting and ending points, and let the computer try to find a path through the maze. There are some sample maze files included to get you started.

The path-finding is accomplished using the A* (A-Star) algorithm, which is provided in a module for speed reasons. The module was coded in "C" using the DevC++ IDE.

To install, uncompress the zip file into your thinBasic UserScripts folder, and copy the thinBasic_ASTAR.dll file to your LIB folder. The SDK folder has the source files the module was compiled from.

I'm not a "C" programmer, so please let me know if I did something wrong in my module.

Known Problems:

I developed this application at home on a Windows 2000 Pro OS, I just ran it at work on XP, and it seems to act a little differently.

I'm having problems with the fonts in the Help About dialog box. Sometimes they render correctly, othertimes they do not.

I'm also not clear on how to handle the WM_PAINT message. I tend to get multiple repaints of the screen when I only want one.

The module is not very well developed. If there is sufficient interest, I will develop it further and make it more useful. I'm not a game developer, so I'm not sure what you guys would want.

Thanks for taking a look!

Randall

Updates:

2007.10.06 main window is now resizable and mazes will adapt to winwow client area

[Petr Schreiber]

Hi Randall,

what a shock ! :o
This is absolutely incredible script and module!

Profi layout, fast execution, even helpfile !

I will check the repaint / font problems ... but this are just details comparing to work you did.


Terrific!,
Petr

[Petr Schreiber]

Regarding fonts,

it seems to me like some resource leak or something.
It should be correct to do something like


DeleteObject(hFont2)
DeleteObject(hFont3)

... when exiting about proc. Maybe something similar for painting, but I am not very good at raw SDK paint functions, so maybe somebody else will know better :)

I must play with your script again and again. Really nice !


Petr

[ErosOlmi]

Randall,

what a present :o
Nice idea, perfect module, professional script complete and well written in all parts. You have spent a lot of time on it, I'm pretty sure about that. I have no words because you have showed to me once again the many possibilities thinBasic and especially thinBasic modules can have.

Regarding refresh rate and some strange %WM_PAINT firing, I'm quite sure it is a problem in UI (User Interface) module. In today released thinBasic preview 1.4.0.1 I have changed some code on how internal UI Windows message pump handle %WM_PAINT message. It makes some positive difference for example with previous one version when window goes outside screen and return, covered area does not get repaint while with current online one it des. But I need some time to understand what I'm doing wrong with %WM_PAINT. So for the moment do not worry about that or at least not too much. I will use this script for testing.

Regarding fonts, I need some more time to study your script and see how things are done.

Thanks again for this present.
I'm sure it will focus the attention for some big time :D
Be prepared to implement thinBasic_ASTAR module ;)

Ciao
Eros

[ErosOlmi]

Randall,

as we are used to do for interesting complete projects like this one, I have created a dedicated forum named AStar and moved your posts into it.

You are also moderator in this forum. Being a moderator doesn't mean anything other than you have some more forum power over posts. So feel free to do what you prefer with your new creature here.

Ciao
Eros

[Michael Hartlef]

Great man! I will still release my path module, the more the better. I will have a close look at yours. Again thank you very much!

[matthew]

Excellent looking program Randall, really interesting. :)

[kryton9]

Randall, I am just amazeD :)

It is so quick and clever. I couldn't fool it yet, probably won't but I will keep trying. Very cool idea for a game and also of course what looks like a neat module to study!!
THanks so much!! Really really neat!!!

[Randall]

Thank you all so very much for your kind comments!

I was only able to create it because of all the sample code and forum posts you all have so graciously supplied. Anytime I wasn't sure how to code something, I could either find a sample program or code snippet in the forums that showed me the way. My thanks go out to all of you for unselfishly sharing your code and expertise. I am honored to add my code alongside the excellent code already posted on this forum site.

Thanks again,

Randall

[Randall]

Great man! I will still release my path module, the more the better. I will have a close look at yours. Again thank you very much!

Thanks Michael,

If you would like to incorporate my code into your path module, please feel free to do so.

Randall

[Michael Hartlef]

My code is developed in IBP, yours in C++ if I read correct. I see no problem having a module for ASTAR and one for DJISTRA.

[ErosOlmi]

Randall,

a possible work around about %WM_PAINT is to clear the message queue of the window using ClearMessages(hDlg) where hDlg is the handle of the window.
ClearMessages(hDlg) is a unique thinBasic command (not a standard Windows behave) used to clear the internal queue thinBasic store for every window. So write something like:


CASE %WM_PAINT
Call Paint_Grid_Window()
Call Paint_Draw_Mode_Legend()
ClearMessages(hDlg)

so script will clear the window message queue avoiding to return so many %WM_PAINT

As I said, it is a trick and not a standard or general behave to be used other than in thinBasic script.
Hope it makes some difference.

I'm looking at UI module in order to find an official way to get it working correctly. %WM_PAINT message are in reality fired by windows but each belonging to different child windows. So I need to trap them all and fire only the relevant ones.

Ciao
Eros

[ErosOlmi]

Forgot to say,

if you make significant changes or fix important bugs, please remove you attachement in first post and attach again the project so other can remain updated.
You can also create sticky posts in this forum because you are moderator.

Ciao
Eros

[Randall]

Thanks Eros,

I'll give it a try this evening when I get home from work.

The GetMessage function has an optional parameter, which is a pointer to a NMHDR structure. Is the ID of the window (control) generating the WM_PAINT message stored in that structure? If so, I could just react to the windows I want, and ignore the rest.

Thanks again,

Randall

[ErosOlmi]

Yes, Randal, seems you got it.

I've done few tests and seems IDFrom in notification structure returns the handle or the ID of the control sending the %WM_PAINT message.
So you need to test if IDFrom contains the window handle.

Thanks about this idea. Seems you know much better than me behind the curtains engines :D
Let me know if it works better than clearing the message queue.

Ciao
Eros

[Randall]

Thanks about this idea. Seems you know much better than me behind the curtains engines :D

Hah! Just a lucky guess on my part. Even a blind squirrel gets an acorn once in a while. :D

Thanks for the information, Eros. I'll give it a try this evening.

Randall

[sandyrepope]

What screen resolution was the program written for?

I run 800 x 600 and the window doesn't look right.

Thanks
Sandy

[ErosOlmi]

1280x1024 or higher here.
But yes, window is fixed size. Maybe, after refresh problems are solved, next version will be a resizable one with maze autoadjusting.

[Randall]

Yes, certainly. The next version will be re-sizeable.

Sorry samdyrepope, I neglected to consider users with different screen resolutions. I will fix it as soon as possible, but it will take me a few days as I have very limited time this week to work on it.

Randall

[sandyrepope]

Thanks Randall. I appreciate your response. I understand about having limited time. I await the update with bated breath. (I don't really know what that means but here in New Mexico USA I hear people say it a lot.)

Take your time... it will be worth waiting for.

Thanks
Sandy

[Michael Clease]

bated breath refers to a state in which you almost stop breathing through terror, awe, extreme anticipation, or anxiety.

[Randall]

bated breath refers to a state in which you almost stop breathing through terror, awe, extreme anticipation, or anxiety.

I always thought it had something to do with fish bait. Thanks for clearing it up for me! :D

[sandyrepope]

I always thought it had something to do with fish bait.

That's what I thought too! I'm sure glad that's cleared up.

Thanks
Sandy