Sign in to follow this  

Quick A* question

This topic is 4860 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

Could someone tell me exactly what heuristic weight and terrain weight is? I understand how and why the given, heuristic and final costs work, but I'm not sure what the weights are. I'm under the impression that if a given map has plys on it represented by say the costs of 1 - 5 on every given ply, where 1 is smooth surface and 5 is rugged terrain, that the numbers assigned to the plys is the terrain weight of that specific ply. And if that logic is correct, I'm assuming that the heuristic weight would be the accumulated weights of every ply from start to goal (or from the current node's position to goal). Please help me if I'm wrong, and thanks in advance!

Share this post


Link to post
Share on other sites
I've implemented A* several times, and i don't know what you're talking about.

Maybe you could post a link to where you got those terms from(heuristic weight and terrain weight), and maybe i could figure out what they are by reading it.

Share this post


Link to post
Share on other sites
Certainly the terminology used is not generalised to the A* algorithm but is specific to the implementation/problem domain that you are looking at (presumably you're looking at someone elses work and trying to understand it for your own implementation). Without a reference to this work, it would not be possible to decipher how that author has applied A* to their domain (which would explain the unusual terminology).

In other words... please post a link to the source material so we can all come up to speed with the terminology and hopefully help you decipher what it means. It certainly has nothing to do with the canonical A* algorithm.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Usually, the evaluation function is just the path cost + hueristic estimate, i.e. heuristic is not weighted, though it would make sense to if you weren't confident in the heuristic. It'd be like uniform cost.

From the sounds of things, the OP is looking at pathing tutorial, though ply is more like minimax.

Timkin, you attend Monash, right? As a student or lecturer?

Share this post


Link to post
Share on other sites
Could 'terrain weight' allow for different types of 'entity' crossing the same terrain? For example a swamp 'tile' might have a cost of 2 with a human having a weight of 1 and a crocodile 0.5. It's a possiblity and it's how I'd do it (bearing in mind I'm a novice) but I'd also be interested in any article you're referring to.

Share this post


Link to post
Share on other sites
Quote:
Original post by Chris Hare
As a student or lecturer?


I used to attend Monash... as a student, postgrad, tutor & part-time lecturer... I then worked for Melbourne Uni and I'm now an Honorary Staff member in the Faculty of Medicine (Monash Uni) and I work (at least for the remaining two months of my contract) for Monash Medical Centre (not owned by the University though) within the University's Department of Medicine. It's a bit convoluted!

Any particular reason this is relevant to the current thread? You can PM me if you want to chat about stuff not relevant to the thread.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Quote:
Original post by tonyg
Could 'terrain weight' allow for different types of 'entity' crossing the same terrain? For example a swamp 'tile' might have a cost of 2 with a human having a weight of 1 and a crocodile 0.5.

Object based programming can do this. A refer to different map can give you the different 'terrain weight'. But remember: at A* this is different map, not different 'terrain weight'.

Share this post


Link to post
Share on other sites
I would assume that you are simply talking about the different "speed values" or "movement costs" for terrain or some such interpretation. e.g.

Road = 1
Grass = 2
Hills = 2.5
Forest = 3
Mountains = 5

The pathing calculations, therefore, are not simply a total number of nodes visited on the current path but rather a total of the movement points expended along that path. In the case above, it would be better to take the 8-space road around the mountains rather than the 2-space path through them (2*5=10).

If that is, indeed, to what you are referring, you can approach it two ways. In both, you total the terrain weights of the current path up to the position you are testing. In one, you estimate the path from current node to goal using the base value (1). That is, the distance remaining to the goal node.

In the second method, you could actually sum the straight line terrain weights from the current node to the goal. That method may yield slightly faster results due to disqualifying some paths earlier... but is prone to error and would take a while to calculate anyway since it is easier to simply calc the remaining distance to the goal as your heuristic rather than walking the path and accumulating a cost number.

If I remember correctly, people generally use the first method.

Share this post


Link to post
Share on other sites

This topic is 4860 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