Pathfinding

[CareyBear]

I recently naively decided to build a 'reactive' mission, which would cover the entire island. This included defenses for captured towns which would be 'built up' over time. Convoys skittering to and fro and so forth. Here we come to the pickle.

Since each town, base or checkpoint may be held by either side, and I've defined four 'Supply Points' where new soldiers and vehicles can rumble onto the island, and since for the sake of 'realism' convoys go only on the roads... How do I find a path that only proceeds through friendly towns? Should be easy, right? Yeah, that's what I thought.

I've run into the pathfinding problem. Apparently. I tried to research it, but ran into a problem. The problem is sentences like these two pearlers.

If n is a goal node, exit successfully with the solution obtained by tracing a path along the pointers from n to n0 in G.
Expand node n, generating the set, M, of its successors that are not already ancestors of n in G. Install these members of M as successors of n in G.

Right. So, since I'm still lacking my Comp Sci PHD, if anyone can explain (or better, show) me how to do this sort of A* search in OFP using arrays, I'd really appreciate it. Anyone tried to tackle this one?

I got as far as:

for each town / base:
town# = marker?
townroutes [town1, town2] where these are connx by road without going through another town or base

where the node marker is the town and the marker itself can be referenced (colour red=east held, green = west held) to determine who holds the town.

Then you have to search by node, building a 'route' array as you go, checking each stop for sides etc. But I get very confused trying to figure out how to make it all happen.

If anyone can help, it would be much appreciated.

[True Immortal]

i tried to simulate a town once, i didnt want all the people to walk using a few move and cycle WP, cause that'll look really gay.

so basicly i wanted to simulate real walking.

i've created Game Logic in every crossroad in town.
and created a script that made the civilian go from crossroad to crossroad (game logic to game logic acctually), and when he arrived to the next WP he chooses where to go next.

i've programed a part for each crossroad where it get a random number and using it selecting which way to go, i've also blocked the going back option.

you could do the same, create WPs (using Game Logic or anything else),  around the map, and for each WP mention by which army are they controled. you can create a WP for each town and make the trucks go through neighbour towns only.

long story, hope i helped =]

[Sui]

Hmm... my qualifications are in Aviation, not comp Sci but here's something I'd try.

For each town have:

• A variable defining which side it belongs to
• An array defining the towns it is directly linked to, that is never altered.
  
• An array defining the towns it is linked to that are friendly, which will be altered whenever a town changes hands

In your script where you change the marker colour, you could also change the variables/arrays as appropriate. There is probably a better way, and I can definately think of some problems with that method off hand... something to try anyway ;)

[Bremmer]

The arrays that Sui suggested are the basic building blocks you will need. The problem arises when you want a convoy to reach a town via a string of friendly towns.

You need some sort of algorithm that checks what friendly towns your destination is accessible from, then what towns this is accessible from (excluding the one you just worked back from of course) ...so on and so on ... until you get back to your starting point.

Ideally you should record all possibilities so you can select the shortest one (might require another array specifying distance between towns).

This is an extremely difficult problem, but one of the most interesting ones I've seen cropping up in a long time. I'm busy at work just now, but I'll give this some more thought later on.

Cheers

[CareyBear]

The problem arises when you want a convoy to reach a town via a string of friendly towns.

Exactly. I'm down with knowing friendly and enemy (using global variables to track - just posted a script in Beta Testing that uses same system), I'm down wid all da *nevermind*

Anyway, it's this pathfinding problem. I read up on it more, still can't translate it into OFP script.

a node is a town (*)
a edge is a road from a node to a node (*)----(*)

Each node may have one or more edges, but not all edges might be valid (might lead to an enemy node)

so, we're searching a tree.

(*start 1) --- (*2) ------(*ENEMY 3)
  \                  \                  \
   \                  \                  \
    (*4)---------(*5) --------(*6)

[1, 2, 5, 6] and [1, 4, 5, 6] are both valid solutions. The second is slightly better since fewer waypoints share roads with enemy territory. This is exactly what I want the answer to look like too that is, an array of stops.

So, the problem is recursive. The simplest solution (and the least efficient - might find a long path before a short one) is to search each node to terminus, enemy, goal or maximum depth. There might also be no path (just to make it fun). I'm using Everon, so I think that ten steps is deep enough to take the search down the tree.

Given the simplicity of the waypoint map I'm using - about 20 total - and the fact that none have more than four connections, I don't want to stop when I find a solution - I want to find the *best* solution. So the best bet is to return all valid solutions that are under ten steps. Could also only return a max number of solutions (replace the mostWP one with a lesser WP one as it's found?) which are the five with the least number of stops. Then step through each finding distance from stop to stop & adding, then sort them by total distance & take the shortest.

As I said, this is one of those few problems which recursion will solve well. But with no user defined functions that return values, have to use a script. It won't return values, but it can set a global variable when it's finished & the caller can @!isNull _var

and if referring to a global variable, that means you need one for each convoy

ok.. script would need to call itself for each level of depth.. so must pass depth to script when called. This idea below might sort of work, but it quits when it first finds a solution

nodetraverse.sqs

[depth, location, destination]
_depth select 0
_loc select 1
_dest select 2
         is goal? -> isgoal
         is max depth? -> noluckhere
         is friendly? !-> enemynode
         put self in [route] at position depth
         get location edges
         for each edge
            [depth + 1, edgenode, dest] exec "nodetraverse.sqs"
            @ !isnull gvarray select (depth + 1)
             returnvalue = gvarray select (depth + 1)
             if returnvalue = goal goto isgoal
             if returnvalue = enemy do next edge
             if returnvalue = nosolution do next edge
          if no more edges, goto noluckhere

#noluckhere
   setgv nosolution
   exit

#enemynode
   setgv enemy
   exit

#isgoal
   set gvarray(depth) goal
   exit


I'm too tired to try and actually work it out right now. I think I'm getting it. *brain fizzles and melts*

Anyone, take a look at that psuedocode and see if you think it would work? Recursive functions are notoriously difficult to code because they're hard to predict.

[CareyBear]

just realised with the above:

isgoal should set route[] to
routes[] (index count routes[] + 1)
(ie, add valid route to array of valid routes) then exit,
so the main loop condition check (on return) if gets a goal return result should NOT call isgoal - should just proceed to the next edge. That way, will check all possible routes and return array of all valid routes. Doesn't need to exit or unset variable below

Might be able to speed it up a lot in practice by only searching to a depth of 5, then searching to a depth of 10 only if a 5 stop route isn't found.

If you're a coder, you know that function efficiency is measured with O(n), which is the rate of increase of processing required as the data set increases. I think that the solution above is actually O(n^depth). Which is terrible, but it's the way it is if you search every single possible solution to a particular depth. This is the old chess game problem - but with chess, there are so many possible moves - such a big data set - that you are looking at obscenely huge numbers of possibilities.

Say the map / data set has 2 edges per node. Searching to a depth of 5 would mean scouring 2^5 nodes, or only 32 nodes. To a depth of 10, on the other hand, means checking 1024 nodes. I might, in fact, limit it to a depth of 8 (256 nodes) - but you all know what 8 bit is.. *L*.

All this to find a way from Lamentin to Morton without going through Le Moule.
Answer: Lamentin, Montignac, Provins, Figari, Morton. Five steps. I think. *brain finally melts into steaming puddle*

[Dinger]

Here's how I'd do it:
Modify Sui's third dynamic array to exclude destinations that do not have further (friendly or not) waypoints (in other words, dead-end towns).
Waste some variables and create an array of towns that are one intermediate stop (along a friendly route) away from the destination town, along with a parallel array containing the name of the intermediate town.
(e.g.,
[montignac, Le moule, le port, detroit]
[provins, provins, Sainte marie, Saint Marie]
If one of the intermediate or 2-stop towns is the origination point, you've got your solution.  use it.
otherwise,
In the pathfinder array, instead of timing out at ten stops, simply construct a path using the third dynamic array (friendly non-dead-end waypoints); before adding a further waypoint to the array, ensure that it's not already in the path array (e.g. at [La Moule, Lamentin] it would not pick LaMoule as a waypoint.  That's a ?_wpcandidate in _currentpath:goto "nextwpcandidate").  Keep going until you hit one of the 2-stop towns or run out of options.  If oyu hit one of the towns, save it to a solution array (with the two stops).
Then take your solution, and check the next option in the list (on the third dynamic array for that town), until options are exhausted.
When options are exhausted, delete the last step in the path and repeat at the next lowest level of the path, until you've exhausted all your options.

Then go through the solution array, and calculate the distance in the route as a function of distance between waypoints.  You can do this either by using distance on the waypoints, or, if you're fancy, you can run tests between each leg with AI and reporting, giving the time between legs.  

[Chudley]

Hmmm, this is an interesting problem.

I have learned that if you come up against a problem in OFP, you can either find the solution yourself, ask someone else or dePBO missions similar to the one you wish to create.

However, I'm stuck with this one.

But, what I'd do is....make one side occupy the north and the other the south.

Then all you got to do is tell the units not go any further than point x.

I realise that this post may be of no use to you, but hopefully it has helped you to see your problem from another point of view.

[CareyBear]

Thanks for your thoughts all. Dinger, great idea about marking already visited.. And you're right, a breadth first search would be better in this situation - but I can't see how to make it work crosswise instead of downwise without having nightmarishly complex data structures to store partial solutiuons. With depth first it's a simple iteration through all possibles, and only considering one possible structure at a time..

Just a note on (sigh) why simple solutions won't work for me in this case.

1) Sadly, I can't copy a mission that's like mine, because there aren't any ;D (big call, prepared to support it. Will post full mission description docco in Mission Ideas when it's more together and closer to beta.. ie, maybe never). Ok, I take it back, If there are any missions like this out there, let me know, I'd love to gut them for their code.. muhahhah.. *ahem*

2) Short description: It's a MP LAN TEAM-SECTOR-CONTROL mission (kinda) over the whole island, with full squads for each player. Played 5v5v0-5 with different objectives for resistance. East/West squads are: Command, Armoured, 1st Infantry, 2nd Infantry, Special Operations. Features reinforcements, garrisons, support and respawning into 2IC. Communicate with Papa Bear / Big Brother (command control for sides) via radio operators, radio tents. Purchase weapons, soldiers and vehicles for delivery to a controlled port, then automated convoy to towns (or helidrop for Spec Ops). PB / BB will offer airstrikes on confirmed laser designation. Can request airstrikes on enemy *locations* (ie, towns) via radio tent.
Victory is determined by: TIMEOUT = two? hours play
Complete Military Victory (hold all sites at TIMEOUT)
Partial Military Victory (hold all bases at TIMEOUT)
Technical Victory (points comparison)
Points, btw, are allocated for taking towns, but they provide points over time. Resistance achieve points for destroying enemy materiel (tanks, trucks, cars, air) and liberating towns.
These points are what you spend when you buy reinforcements and vehicles. Resistance can't buy vehicles, but they can buy weapons from arms traders. Oh, yes, I'm expecting this to require a dedicated server. *OH REALLY?*  ;D

Ok, that's a short description! of the mission I actually have a 50 pg word file detailing all the above, actions, scripts etc for much of it. Working title: For Everon

Most of the above is easy, and simply a case of modifying scripts already in OFPED's database, like halo scripts, Dinger's funky 'catch laser dot anywhere' trigger trick, etc

3) I need to be able to find a path from anywhere to anywhere. Any town can be taken by any side. Convoys need to be ready to dodge. Just like real life.

4) The pathfinder can't modify global variables, can only read them, except for it's return values. That's becoz the basic place[] variable I refer to is the responsibility of several scripts to keep updated: garrison.sqs and advancedcapture.sqs. I don't want it updated to include only links to friendly towns, because I can get that information on each node with a function call (that's why I used getmarkercolor)

I like the backwards search idea too. It's a pity that user def functions are so primitive, and there aren't really any string tools. I have to use a single function to return the answer.

I'm pretty sure (now I've had some sleep) that my solution above will work - with a lot of work, as it's guaranteed to return the *best* route. It shouldn't be called too often - only if a soft target wants a destination.

Ok, I know fudge factors are a way of life due to the limitations of OFP scripting, but I want to use *as few as possible*.

I'm trying to make this as smart as possible, so that when the player pulls a blitzkrieg out of their military issue jockstrap and takes three towns, the AI supports them. If they order reinforcements, they will be delivered in a realistic - or at least consistent - fashion. That's what it's for. Five guys with a squad each do not a war make, and indeed, they only scratch the surface of the strategy that OFP is capable of.
It all needs to be as general as possible becoz the same routines will apply to each side, & I want it to still make some kind of sense when the player does something I never expected.

CE2, for example, is genius, but it's SP only, and what makes you think I want to be in *charge*? Sod that. I want to blow things up. I want to infiltrate past enemy patrols and satchel charge his convoys. I want to hide in the shrubbery and laser designate my brother's command T80, and give him a Maverick surprise. I want to cut supply lines, overrun defenses, steal enemy equipment, deploy snipers on enemy patrol routes, keep them on their toes.. and I want it all to contribute to the overall war. And all in MULTIPLAYER - so they're doing it to me too. Carnage.

Ok. No one is allowed to hassle me about when it's going to be done, or I'll give them some work to do on it
Something fun :p , involving long lists of X & Y co-ords.. *L*

Cheers all, and sorry for making you read so much incomprehensible crud..  

[Sui]

Right... modification of my previous method...

The second array, the one with all the direct connections that never changes? Scrap it.

Replace it with a (admittedly huge) array consisting of all connections, including (in some cases) a couple of routes. So, your master marker array might look something like this:

MarkerRA = ["Airbase","StPhillippe","Meaux","Tyrone","Gravette","EntreDeux","Montignac"...etc]

If your convoy was at Everon Airbase, the array for that marker might look somethinglike this:

_routeRA = [ [

• ],[ [1] ],[ [1,2],[3,2] ],[ [1,2,4],[3,2,4] ],[ [1,2,6,5],[3,2,6,5] ],[ [3,6] ]...etc

So every number in there corresponds to a marker in MarkerRA (eg. 0 = "Airbase", 3 = "Tyrone" etc.). In that array you've got all likely routes to get from the marker you're at to any other marker on the map. So to get to Montignac, we go to the 7th term:

[ [3,6] ]

Which says we have to go through marker 3 ("Tyrone") and marker 6 ("Montignac", the destination). The reason it's an array within an array is because you can include all the routes, such as in term 3:

[ [1,2],[3,2] ]

Which says the quickest route is through "StPhillipe" to "Meaux". The alternative route (the structure makes more than one alternative possible) is through "Tyrone" on to "Meaux".

You'd check the routes with a loop like this:

_i = 0
#getdest
~0.01
? "getmarkercolor _x == red" count ((_route select _destination) select _i) == 0: goto choose this route
_i = _i + 1
? _i < count (_route select _destination): got "getdest"
choose new destination

Dunno... this is just something I thought up in the shower... it would take some serious work to get going. It would probably take you about a week just to write all the arrays!
However the possibilities are limited only by how long you can be bothered writing them

Just another crazy idea....

[edit] The bloody thing took away all my square brackets :eyebrow: [/edit]

[CareyBear]

Hey Sui, that's a great idea.

Unfortunately, there are (say) 20 markers. So there are AT LEAST 20x20 routes. There's usually more than one way get somewhere, too. So say 500 routes.

Can you imagine trying to debug that array?  :-X

I will keep that idea in mind for the first version of this map (title: Limited War) which should only have six or seven locations on it. If I can't get a general solution done, I'll try your trick - there'll only be about 30 odd routes.

I hate exponential problems. They eat your CPU.

If I can get this node / tree approach working.. The comp will generate the routes..

I might have to add a fudge factor to each edge (if it's a windy road) because distance gives you a crow flies distance, not a real distance - ie: Levie to Lamentin is two stops via Montignac and three via Morton, but shorter via Morton - but distance gives similar values.

[Bremmer]

I definately think it would be worth generating a more general solution rather than Sui's idea of listing all possible routes. This way the script can be used for other islands with only minor modification.

I started having a look at the technical problems this morining, but have run into the problem of unknown depth. My idea was to use loops to assign routes into solution arrays, but it would appear that I need a seperate loop for each level of depth. I guess I could just put in more loops than would possibly be needed, but it seems horribly clumsy.

Incidentally - is it better to generate all possible solutions at a particular level of depth before moving on to the next level, or generate a complete route then go back and start from the beginning.

This is a real brain melter  :-\

[CareyBear]

Yes, you need a seperate loop for each level of depth, or a recursive call. That's why I made that example one above only one loop which calls itself, but keep track of the depth..

The question of which is better - depth first or breadth first - depends on the type of answer you're looking for. I picked depth first cos I could see a way to do it with recursive scripting. I don't know how do do breadth first without holding all considered possibilities in memory the whole time. Depth first on nodes can be done with only one array (currently considered route) and one array of results (array of valid routes to destination).

You don't have to go back to the beginning. You can just copy the route you've constructed and then step back up one depth & continue searching where you left off, until you have no more possibles to consider.

Also, I think any time a node is expanded, it should be added to a checked[] array, then each node compared against the checked[] array so that a node is not checked twice. This will make it massively more efficient. With this added, the number of possible routes is about places2

I realised that, if you don't do this, you end up testing routes which read like [1, 2, 1, 2, 1, 2, 3, 4] valid 1-4 in 8 steps. *sigh* Only computers can be this annoying.

(ie, if I go from St Pierre to Vernon, I can go to St P or Durras - but I don't want to go to St P, nor waste time checking that route)

I will try and write this general solution up, since all it requires is a few markers & a simple data structure to find it's way around - I'm sure it will come in useful. I've been trying to debug a totally different script atm.

Don't you love the ones that work.. sometimes? Or even better, work a few times, then stop working till you restart the mission? And to top it off.. 'few' is variable here. *bangs head against desk* *goes off to play Red Hammer: Rage again*

[walker]

Hi CareyBear

Sounds a bit like the dynamic strategy I used in BS06. But what you are doing is creating a true AI to drive the dynamic element BS06 is programmed only.

Some useful tips though.
Some work can be done placing guard triggers over target areas turn these on or off as to who is in control. Then just let the OFP AI deal with sending apropriate units that you have set to guard that is what I do with some of the units in BS06.

A quick and dirty method would be to create a table of priorites. In a script have an array giving the route to each priority of target.

Use triggers like the guard triggers to show a script the status of the target.

Set up in a tree structure in a set of arrays to show the different possible paths to objectives. It also nice to throw in a random element.

So you have a decision tree to priortise strategic targets and the tactical path to those targets.

Use the method I used in BS06 to give dynamic waypoints to the Ai with game logics but add in a minute cycle loop at the end with one seek and destroy waypoint or a guard waypoint or hold waypoint and a cycle waypoint. This last two waypoints you move to you desired target area (make the waypoint area 100m) Mix the types of waypoint with diferent units to increase or decrease the random nature of enemy AI reaction.

The best method would be a true neural net (Denoir Confucious Uiox and several others are working on this over at the CoC.) Combined with a either a programed table of map square values or a topoligcal description of square values ie a town square is of higher value than a flat bit of land, land with a higher elevation is worth more, Forest is worth more than open ground, etc seek to control the land with the highest value.

Kind Regards walker

[CareyBear]

Fortunately, I'm planning all this as a MP mission, which means that I don't have to worry about AI strategy.

And I'm becoming aware that this is the sort of problem people write their thesis on. *sigh*

Good news is that I have a solution in OFP. Bad news is that it doesn't work properly yet. I will post it soonish if I can get it to work. And probably if I can't. If I can't get it to work properly I'll post it with copious notes on what it's supposed to do.

Probably after the weekend.

Again, good solution walker, but I'm set on a general solution. And, more to the point, if I get one done, all you need is a data representation of your map and you can adapt it to run that sort of strategy (would just need to change the exit conditions to suit your data array)

So, I'm keepin on keepin on at it. I really want to get this to work now. It'll be incredibly useful for reactive mission design.

[DrStrangelove]

1 Comment:

How do you travel by car through a country that has thousands of cities ? Are you travelling city to city ? No.

You travel through states. You *mostly* won't need to worry about the city you need to get to at first because states are *mostly* connected by major routes.
You've got time to think how to get to the city when you're in the destination state.

In OpF Cities are the little towns. If there are too many of them to get a solution just search for a way to use big sectors (states) instead. Search the main route and try to put all alternative routes into sectors.

If this is possible you'll get a much simpler solution at first. When you got ur destination sector, you need a 2nd calculation how to get to the destination city, but the advantage is that you only need to calculate within a single sector.

It's like guessing a certain number somebody chooses out of 1-1000. How to do it ? Start guessing in big terms (states/sectors): "Is it 500 ?"

"Naah, it's lower" (This is your main target sector)

"Is it 250 ?"

"Lower"

"125?"

"Higher"

"188?"  (125 + 63)

"Close, but higher"

"190?"

"Yep"


-------------
Just an idea. It depends how good you can organize cities on the map + their connections into bigger sectors.

[CareyBear]

[attachment deleted by admin]