Member Avatar for GhostMonkey

Hey, I've got a list that takes in the current co-ordinates from a board. I'm trying to sort that list using the Manhattan distance heuristic but I'm not sure how to go about it. My list is simply

list<int> list1;

With the formula by which it should be sorted is:

f = g + h

Any help would be greatly appreciated :)

Edited by GhostMonkey because: n/a
  • 3 Contributors
  • 6 Replies
  • 103 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by raptr_dflo
Member Avatar for L7Sqr

As I understand what I've [just] read about Manhattan distance it is a comparison between two points. That requires at least 2 x-values and 2 y-values. How do you expect to sort based on that requirement with just a list of int values? Or have I missed something entirely?

Member Avatar for GhostMonkey

Basically, there's a starting point, say (0,0) and an end point (5,5). I'm trying to get to the end point by moving one space in each direction NESW and seeing which move was closer to the goal. So using the Manhattan distance to sort the list of positions, I can determine that going East and South are the best options so I would put them to the top of the list. The goal position would be x2,y2 and the current position would be x1,y1. Problem is, I dont know how to sort the list.

Member Avatar for L7Sqr

If there are no obstacles then so long as you move away from the origin and towards the goal on every move (in whatever direction you want) the distance is the same.

It sounds to me like you are more hung up on trying to determine - for arbitrary points - what constitutes 'away from origin' and 'toward goal'. For that you only need to consider two comparisons:

  • is x1 > x2 ?
  • is y1 > y2 ?

There is a special case when either of the two of them are equal and in that case the outcome of the second equation will tell you how to move.

Member Avatar for GhostMonkey

I think you're missing the point somewhere but I'm not sure where :P

The algorithm is f = g + h, g is the number of moves you've made and h is the heuristic, (xposition-xgoal)+(yposition-ygoal). If you move closer to the goal f will increase, if you move further away f will decrease.

So anyway, how do I use this to sort a list?

Member Avatar for L7Sqr

Ok. You've declared two inputs and an output: g , h and f . A list holds a single value. You can provide a function that takes a value in the list (and the next), makes a computation and returns a result but I'm not sure what you have stored in the list so I can not help you there.
If all you want to do is sort the elements in the list from lowest to highest just use list.sort . If you want to use your formula use list.sort(FormulaFunction) .

here is a reference

Member Avatar for raptr_dflo

And you still can't store 2D coordinates of the form (x,y) into a list<int>. Perhaps you need a structure like:

struct PointWithDistanceFromKnownPoint {
    int x;
    int y;
    int manhattanDist;
};

And then form a list of those, and provide a "comparator" to the list.sort() function.

If we're all still confused about what you need, consider the possibility that you haven't expressed your problem clearly. Feel free to post the text of the assignment, if that will help clarify your needs.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.