[SOLVED]How to modify the heuristics of the A* pathfinding?

Shekerev · Wed 02/12/2009 20:18:20

Hello

Greetings:
I am relatively new to AGS and totally new to the forums. So let me first express my awe to the great amount of work put into this project and comunity :o

Now what I want to achieve:
* a field of squares, where EACH square is walkable
* many characters at the same time on the field
* every square can contain resource that caracters want to collect, dangers that will hurt the characters a little bit, or none
* every square can be solid
* solid squares are walkable, just take more time to dig through it and make the square normal
* initially all squares are solid (characters dig tunnels like rats)
* each character has parameters about how inclined he is to dig or let himself get hurt by a danger in expense for a shorter path

Problem:
As of this writing I didn't find any info on how to set the heuristics of the A* when the sorted queue is expanded. I want to add to the cost of each node also its cost in contents (resource, danger or normal) and its cost in speed (normal or must_dig) for that particular character.

Question:
Could you please forward me to a solution/module/plugin that can help me?

Disclaimer:
The task I am currently after is the core feature of an action-adventure game I am developing. Dropping it will practically make the whole project redundant :'(

So it would be of great help to know if it is even possible to do in AGS?

PP: sorry if this question is already cleared elsewhere, tried my best to read everything about AGS pathfinding

PPP: sorry that my first post is a question rather than some help

Pumaman · Wed 02/12/2009 20:24:00

AGS does not currently allow you to modify the pathfinder algorithm.

Depending on what you are trying to do, you might be better off implementing some sort of simple pathfinding algorithm in the script.

Shekerev · Wed 02/12/2009 20:35:58

Implementing my own pathfinder is not really an option - I need efficiency and my sorted queue will suck lots of time

About the project:

I'd like to make a war between 2 tribes of entities - about 400 purple and orange dots. They gather food and avoid fires and dig tunnels.

It is intended as a bit of scientific work about abstract evolution and you (player) as an active element in it.

AGS seemed like a natural choice - inventories, dialogues, GUIs, events, all the boring stuff already implemented.

Oh well, I can't have everything

Edit: my bad, sorry, I forgot to thank you for the quick reply !!! Keep up the cool projects!

DoorKnobHandle · Wed 02/12/2009 20:41:28

I implemented A* pathfinding several times in AGS script (most of the times for my realtime strategy game) and it's pretty straightforward and - using binary trees - reasonably fast. There's no other way if you need custom pathfinding.

Pumaman · Wed 02/12/2009 20:55:03

Quote from: Shekerev on Wed 02/12/2009 20:35:58
Implementing my own pathfinder is not really an option - I need efficiency and my sorted queue will suck lots of time

Welcome to the forums, by the way!

If you're familiar with other programming languages you could write a plugin in C++ to do your pathfinding -- although the AGS script is compiled to bytecode so it's reasonably efficient.

dkh, impressive stuff!

Shekerev · Wed 02/12/2009 21:12:32

Quote from: Shekerev on Wed 02/12/2009 20:35:58
Implementing my own pathfinder is not really an option - I need efficiency and my sorted queue will suck lots of time

No, no, I expressed myself in a wrong way. I suffer from a bad case of newbieness so I doubt my own algorithmic skills, not AGS efficiency

dkh, I reallize that I am getting really impudent here but since you've done that before, would it be a problem to post a fragment about how would A* look in AGS ?

DoorKnobHandle · Wed 02/12/2009 21:24:01

I can send you the code but it is a somewhat advanced topic and if you're not experienced with the language and AGS yet then I don't really think it'll help you. In addition to that the pathfinder code is somewhat connected to the code for the tiles in my game, so I can't just send you a neat little module unfortunately.

Still, let me know if you want me to send you the stuff via PM.

Crimson Wizard · Wed 02/12/2009 21:32:28

I made this sort of pathfinding for a 3d shooter based on modern Doom/Heretic/Hexen port engine. It was supposed to do almost same costs as you mentioned - danger, speed, passability. Problem is I never tested its full functionality, mainly because our team postponed the project for some time (it was non-commercial, for fun only

).

I am not quite sure what exactly are the difficulties you have... Do you need this pathfinding from scratch, or you have it already but have troubles with some details?
Well, I see dkh offered you help, so I could be a just backup plan for giving an advice

Shekerev · Wed 02/12/2009 22:03:29

You guys are awesome, thanks for all the replies!

So quick, I'm in enthusiastic mode, back to work

dkh, I sent you a PM, thanks a lot!

Crimson Wizard · Wed 02/12/2009 22:52:05

Quote from: Shekerev on Wed 02/12/2009 22:03:29
dkh, I sent you a PM, thanks a lot!

Hmm... are you sure you sent PM to him and not to me?

Or you sent two PMs?

Shekerev · Thu 03/12/2009 08:33:42

Both of you

Wanted to avoid me flooding

, sorry if I made a mistake

Thanks a lot to everybody, will post more about the game when I have something significant to show

hedgefield · Thu 03/12/2009 22:30:48

Cool, I'd be interested to see what you make of it. A* seems like a pretty advanced algorithm for AI behaviour which I'd like to know more about. It's not exactly a Google-friendly term

DoorKnobHandle · Thu 03/12/2009 22:36:30

largo, check this article out, it's pretty decent: http://www.gamedev.net/reference/articles/article2003.asp

hedgefield · Sun 06/12/2009 20:35:33

Awesome, thanks.