Sort a list?

[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 :)

[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?

[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.

[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.

[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?

[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

[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.