students looking for help with peasant/road system

[bozmir]

Dear community,

As 2 students from the Netherlands from the HKU game design & development. We are looking for some help to create a road/peasant system.

The result should be peasants taking random paths (using waypoints). The road itself has to be buildable. They have to take random paths to get to a specified target. Like a bakery or a house. (they can go off-road if the priority is high enough)

The problem is we dont know how to create buildable waypoints or create an AI for peasants to randomly change their routes depending priorities.

It is a big challenge but essential for our project. You will be credited!

 

[overload119]

Assuming HKU is some institute for game design, I'd imagine you'd figure out a way to do this yourself. Can't you ask your professor or something?

Anyway, you could try an array of location, and an index. The index increases each time a waypoint is created. The peasant will have access to this array, and you can code it to move to any of the locations you want.

 

[Dr Super Good]

You can set waypoint desternations via triggers, just do that on construction of the building.

The roads is slightly different. What I would do is the usual way pathfinding is done, break the roads as they are built down into nodes which can be quieried. Each node represents a split in the road or the end of a road or waypoint on a road. The problem here is the efficency of quiering this data to find the shortest route from one node to another however I have seen such a system of WC3 campaigns although it was slagged for its lack of efficency.

Each node stores. . .
The actual position of the node (via location or X/Y set).
The relationship with other nodes (a list of all the other nodes connected to that node).

The problems with efficency which hampers this system are. . .
No dynamic native list structure in WC3 like in python or java resulting in use of hideosuly slow hashtable systems or limitied sized array systems. This is a problem due to the mn relationships between the node type and itself inorder to find valid node targets.
The lack of multi threading for WC3, meaning that the game engine and AI all have to run off the same thread. Expensive opperations are less noticible if you can run them on another thread on another processor while the game engine does it stuff.

For a hundred odd units it should be doable. You will have to use hashtables I am afraid to do the mn ratio which is where a large ammount of the slowness will occur. Not being familiar with how pathfinding works exactly I can not tell you an algerthim to do it efficently but I will keep thinking about it.

 

[overload119]

Check this resource for pathing algorithms.

http://www.policyalmanac.org/games/aStarTutorial.htm

 

[N-a-z-g-u-l]

I dont know whether you are allowed to use tricks like these, but heres my idea:

On map initialization, loop through the whole map and disable pathing for AMPHIBIOUS_PATHING for example... dont forget to start seperate threads for each line for big maps (ExecuteFunc("funcname"))... The size of one pathing-"block" is 32x32, so you start at border+16 and add 32 each step

then, when a road is built, enable pathing there again. (in a small area around it)

Your peasants then use amphibious pathing and warcraft will find the way on its own... however, its the shortest, and not a random way then, and they are unable to leave the road... By disabling the units pathing "SetUnitPathing(U,false)" (or was it true?, im not sure, there was something weird about this function as far as i remember), they can also leave the road...
I did not experiment with it long enough, but though pathing is disabled, they only leave the pathable area in some cases, so that might be interesting for you. Giving new orders to the peasants periodically would cause them to stay on a road when they cross it (probably), and giving orders to random places near the target as long as the peasant is still in some distance, it could also lead to a random way...

no clean solution, i know ^^

In any other case, A* is the way to go, yes. If you are lucky enough you find an implemention of A* for warcraft somewhere...

http://wc3jass.com/viewtopic.php?t=3581
maybe you can contact this guy personally (forum is quite inactive)

 

[bozmir]

Thanks for all the help! This definitely gave us some ideas. And yes some teachers already helped us out.
We tried implementing some A* systems without much result.
Found some coders at school so i hope they will figure it out ^^
The problem remains unsolved though.

cheers