Currently developing a prototype for a action / sim game in wich you build a castle and defend it from attackers.

the base unit of a fortress is the peasant, this unit builds your castle.
You assign task you wish to be done, like "build a wall here" or "dig a hole here". The peasants then look at the task list, reserves a task and then try to perform it.

The problems im having rises when a peasant cant complete a task ( ea. the peasant cant path to the task. and not being able to path will happen often )

The peasant will reserve this task, wait for the path to calculate then tell the task manager that it failed with the task. The task manager moves this task to the back of the task queue. and the peasant asks for a new task.
I thought this would work fine, but sadly this will create a task deadlock with a very high frequency.

i would just like some input to get my thoughts moving again :)

Can the pathing failures be permanent? As in "can't get there because there's a wall in the way" as opposed to "route blocked by other peasants"?

If so, first thing is to note the difference. For each task, for each peasant which has a try, have them record that they tried it and why they couldn't do it.

When a peasant can't do a task, it doesn't move the task it just goes on to try the next on the list. If the peasant finds a doable task, they do it and start at the front of the list afterwards.

If a peasant gets to the end of the list, they look at the whole list. If any single task failed by being temp blocked, then the peasant removes all their tags saying temp block and sleeps for a while. When they wake up they can have another go at each.

If all tasks failed by being permanently blocked, then the peasant is probably walled in.

If a task gets N attempts by different peasants all of whom can't do it because it's perm blocked then the task is walled in.

In both those cases you probably want to alert the player or manager AI.

So another thing to do is to make sure you can resolve path conflicts. An easy way to do this is order your unit types. Knights probably beat Archers, Archers beat peasants.

If you then number each unit as you create it, that can be used as a tiebreak. This means that in every path conflict (eg; two peasants meet face-to-face in the same narrow corridor) one can force the other to back up to solve the lock.

If the task is not possible (for instance you walled yourself in) then the peasant should tell the task manager to cancel that task and put it on a stack with failed tasks (if so needed).
You might even want to tell the task manager WHY it failed.

peasants doesnt block eachother, so the problem is when the path is unreachable ( beacouse of cliffs ) or it is walled in.

another thing is that the player will create alot of blocked tasks. for example, the player wants to dig a tunnel. he will then create a length of small "dig here" tasks, where the majority will be blocked from the start.

You can treat the tunnel building as 1 task with several subtasks (digs) and either cancel the entire task if one of the digs is unreachable/undiggable or you just cancel the subtasks that cant be performed.

If you can determine a priori who can perform which tasks, and how long it will take each person to reach a given task, then you may be able to treat this as a worker assignment problem and throw the Hungarian algorithm at it.

@Emergent
Maybe it wasn't you but I'm pretty sure I saw someone mention the hungarian algorithm on a different thread. That thread, you were spot on as it was about targeting (as in shooting stuff). The OP's post wasn't about choosing a task (as I took it), but rather what to do when the inability to get to something is permanent rather than temporally impossible. (also, the hungarian algorithm runs in O(n^3), and in games, I think if I want the optimal solution to a problem and I want a good framerate I'd rather just have a priority system where units have a priority factor in addition to specific tasks they look for automatically)

As I see it, there are several types of tasks (in a game like the Sims):
Tasks the user gives to the unit (if these fail, they should be removed from the list of tasks entirely, but when they are added, they should be of the highest priority)
Tasks the environment gives to the unit (these should be given as follows. choose two units at random from your list of units and give the task to the unit with the least time till the end of queue + time to get to the other task, the unit chosen with the highest likelihood will be the unit with the least to do/most likely to do the task soon) (if these fail, check the environment, then repeat the selection process)
Tasks the unit gives to the unit (iterate through all your units, check their needs, put their needs at either the front of the queue, aka self sufficient family, or right after the player's needs, gives more control to the player) If these can't be completed, just remove them entirely from the queue, but give the player a heads up.

they way im doing it now is to let the manager path to the nearest possible task from the peasant. this way i also get the path the peasant need to take.

this works really well at the moment, im not so sure about it when multi-goal tasks is needed