Follow us
Elk News - the email newsletter
Subscribe to the Elk RSS feed, including blog posts, pictures and videos.
Titles only
Full content
Comments aren't included in these feeds. For them you can click the RSS icon in the Recent Comments box.
Our videos at
YouTube
Vimeo
Comments
Marked with white is the area A* has to eplore before finding the path marked with red. It starts from the north, desperately exploring that peninsula, but as it turns out to be a dead-end, it then has to go into all directions until finally finding a way around that bay on the nort-west corner of the lake area.
It is moments like these which really show the incredible computing power of human perceptory system. For a human eye it is immediately self-evident that exploring to the east and north is inefficient because there won't be a way around in those dircetions. But a computer has no way of knowing it, unless it scans the map pixel by pixel...
Hello Erkka! When I read your comment I remembered a Youtube video by Tynan Sylvester explaining a pathfinding system which is labeled Region System: https://www.youtube.com/watch?v=RMBQn_sg7DA. The video is pretty long, so if you are short on time I recommend starting from 8:50. Hopefully this helps or sparks some ideas to the problem.
Sounds interesting, I'll take a look in the evening. I was thinking of a system which would analyze for example areas of 8*8 tiles, and give them values like 0=easily passable ... 5=blocked, so then the A* wouldn't need to scan everything tile by tile, as it could navigate that pre-calculated grid of 8*8 blocks, going into details only when needed. So, it will be interesting to see if that video has some other ideas which are new for me.
Right now I'm having a short break to warm my fingers, after skinning and butchering a ram outdoors.
Is it going to be a new UrW script for NPC, or it's too early to ask? :)
Yes - a proper pathfinding is an essential element we need to get done, before we can implement things like foreign traders arriving at coast, trekking to a market place, doing the bartering and then returning back to their ship and leaving. No more NPC's wandering around in an aimless and random fashion - we would like them to move with a purpose, coming from somewhere, going somewhere to do something. A band of Njerpez leaving their home, travelling to Kaumo, raiding a house and returning back with their loot - a stealthy player could in-game follow the band, ambush them and bring back the loot. All that kind of things to make the world more alive. Many of this kind of stuff relies on a reasonable pathfinding which would be able to navigate in the urw world, crossing rivers and finding a way around lake areas - and making decisions, either choosing the fastest way, or preferring forested areas where it is easier to stay hidden.
If I may be so bold, I don't think algorithmic path-finding is your best solution to implement more realistic NPC 'ambient' behaviors. Certainly, path-finding becomes important when NPCs are interacting with a player however, less granular solutions would prove more useful and probably be more beneficial on a strategic level. For instance, a player doesn't care about the exact path an NPC took to get from his home in village a) to the market in village b) UNLESS he plans on interacting with said NPC somewhere along the way. Say, to rob him somewhere between a) and b). So, for the purposes of a developer, we would only be interested in knowing the probability that a player will have of interacting with a specific NPC at a specific TIME in a specific PLACE. This can be abstracted into algorithms meant to simulate the NPCs behavior. The cool thing is that if you properly utilize an PRNG in conjunction with good simulation algorithms you can use ONE seed to store all the behaviors of ONE NPC for his entire lifespan. In this way you can skip the path-finding altogether UNTIL the probability that the NPCs and the Players will interact becomes very high.
So essentially, what I am saying is that 90% of the time you only need to know that NPC a) is doing Task b) near location c) at time d). And, so knowing every little step the NPC takes for 90% of his time is WASTED effort.
Hope this helps.
Yup. But we still need something for that 10% :)
Add new comment