Depending on how you want to model the problem, you can approach it in several ways. Since it seems like you are working with an imaginary 2D plane I will start with the most relevant options.
Arrange waypoints.
Obviously if X comes before Y, then with lower precedence if X is easier than Z. You will need a difficulty function which will depend primarily on distance to the waypoint, which means that you will probably need to calculate the path from every other possible waypoint and then calculate according to the path. (Though I may be missing some nice method to solve this).
EDIT: To clarify, you need to determine the best order of steps, first in relation to one another (if Y requires X), and then in order of optimal path (see below). This isn't an algorithm, it is a necessary prerequisite for further calculations. If you don't do this then the brute force method below will be extremely resource hungry.
A* path finding (to calculate difficulty from each 'end point').
By 'end point' I mean the initial location and the location of every other objective. This method is inefficient, especially when you have lots of waypoints, but it has obstacle navigation built in if you need it, and once each waypoint has a path length value relative to every other waypoint, you can use simpler functions to approach the objective sequence.
EDIT: This is useful instead of drawing a direct path in the case of obstacles. It will calculate the shortest distance from point A to point B with and without obstacles in the way.
WIKIPEDIA
Brute force paths.
This is a starting point for what should be a better algorithm. Calculate every possible configuration (I would use a branching method to simplify the concept) and remove less optimal ones after calculating scores.
def NextStep(Plan,Steps,ID): ##Warning: written at 5AM. Run at own risk.
if len(Steps)==0:
print "Possible plan: ",ID; ALL_THE_PLANS.append(Plan);
return;
for s in Steps: ##Uncomment next line for multiple people.
#for ppl in PEOPLE:
temp_plan = Plan; temp_steps = Steps; #Use ID.copy() for objects.
temp_id = ID+"Then "+ppl+" does "+s;
temp_plan+=Steps[s]; temp_steps.replace(Steps[s],""); #Or .remove
NextStep(temp_plan, temp_steps, temp_ID);
#This will recurse until all possible arrangements are calculated.
Once you have a list of all paths you can remove those which break the rules (ie Y before X). Note that it helps to do this BEFORE calculating the paths, but it is still very slow and you should try to rewrite the above code to skip illegal plans.
PPL = ALL_THE_PEOPLE_IN_THE_GROUP()
for P in PLANS:
p = PLANS[P] ##Just makes my job easier...
STEPS = p.Objectives ##...And the code looks nicer.
##Assume that all PPL have .Location == START_POINT
for O in STEPS:
p.DIST+=AStar(PPL[O.Person].Location,OBJS[O].Location).Dist;
#Add the distance that the person will travel from their last
# location to the objective to the total distance of this plan.
PPL[O.Person].Location=OBJS[O].Location;
Now just use some imagination... Get the PLAN with the smallest DIST.
Other approaches.
You could also model the problem mathematically and try using other optimizing methods here. I'm not sure how applicable any of these are since it is 5AM and I can't think of ways to remodel your problem, but I will make you aware of them in case you aren't in the hopes that someone benefits.
- Neural networks
- Finite State Automata
- Genetic algoritms
- Minimax (probably only applicable in a 2-player version)
Hope I could help!
