A roguelike game inspired by the literature of Jorge Borges, Umberto Eco & Neal Stephenson, and the games Europa Universalis and Dark Souls. URR aims to explore several philosophical and sociological issues that both arose during the sixteenth and seventeenth century (when the game is approximately set), and in the present day, whilst almost being a deep, complex and highly challenging roguelike. It explores questions of philosophical idealism, cryptography, linguistics and the writing and formation of the historical record, and will challenge players to hopefully think in ways and about themes that are rarely touched upon by games.

Image RSS Feed Latest Screens
New screenshots New screenshots New screenshots
Blog RSS Feed Post news Report abuse Latest News: Crowd Mechanics and Pathfinding (Part 1/2)

3 comments by UltimaRatioRegum on Jul 5th, 2015

This week I’ve been developing the crowd mechanics, and it’s going well, but first we need to talk about how exactly I need this to work:

We have two levels of resolution: the map grid the player is walking around on, and then every other map grid (in the 250×250 tile world map) which is not currently loaded. Therefore, any NPCs who are important but are not currently spawned must be tracked by the game when they’re on a non-loaded world map tile. This, of course, gets very complicated when you have an important NPC start on the loaded map tile the player is walking around, and then step off that map tile onto another… and then how do we track them over, say, 50 turns if the player THEN decided to follow this important NPC onto another map tile, spawning that tile (which the NPC has been walking in, even though it hasn’t been spawned)? Well – for the time being we aren’t worrying about that, although I think I have a good solution. What I’ve been doing this week is getting the standard crowd spawning and walking around sensibly in city districts, which means Lower-Class, Middle-Class, Upper-Class, Military, Market, City Centre, and Religious districts (docks and castles are still not spawning; castles will be coming 0.9, and docks either 0.9 or 0.10 depending on how development plays out).

I tried a few systems last week where NPCs could walk freely around the map without paying attention to the roads, and this ran into two issues. Firstly, having 100+ NPCs moving at once was necessary for the city districts to not feel like a ghost town (even if I made sure the game slyly spawned/de-spawned NPCs around the player to give a false impression of greater density) and this, on 200×200 maps, was beginning to cause minor performance issues; secondly, it just didn’t look very interesting, and there didn’t seem to be any real method or deliberate action to what NPCs were doing. If you trailed them until they hit their target location, they’d just then choose another location, and repeat.

So, this new method had three logics: firstly, to create a form of pathfinding which doesn’t actually need the game to calculate paths to reduce CPU usage; secondly to make NPC movement seem more deliberate; and thirdly to allow NPCs to “path” (or rather, fake-path) towards the gates at the edge of cities, and thereby withdraw themselves from the map if the player trails them long enough, rather than just continuing to identify new locations on one map which they are allowed to travel between. So, I got to work.


The first step (above picture) was to identify areas of the map which a) any NPC could walk (light green), b) which any NPC could walk on and which were curves in the road which the NPCs would have to stop walking straight to traverse (yellow), and which only certain NPCs would be allowed on (dark green) for each of the seven current city districts. There are also some areas of the map which aren’t roads which are blocked to some NPCs (like the courtyard in a mansion, for example), but those aren’t integrated just yet. I created this secret road map, got NPCs spawning on roads, wrote a bit of code for them to be able to identify another road coming off the first road, and let it run.


The first trials would up like the above picture. NPCs spawned on roads, and could sometimes path correctly… but they were always looking for other branches of the road networks they could move onto, but seeing parts of the road they were already on as being a “different” road, and therefore they kept flicking uncertainly back and forth between hundreds of subjective “roads” which, to a human player, would be obvious.The next step was to add a road_direction variable (basically the same as the player’s facing variable) where they keep track of what direction they have been moving, and they can’t read a “road” into their current direction, or their opposite direction, and thus will only detect new roads to explore if those roads are at right-angles. I then upgraded the code for the curves, creating hidden “lanes” for the NPCs to path along:


Which can be usefully compared to the overall pathfinding map for the same district…


…for when we come to NPCs moving off the roads.

Anyway. With that fixed, I upped the number of NPCs, and we got this wonderful image:


This looked cool, but it was a bit too dense, and they looked too similar all sticking to the road paths rather than diverting. We’ll be coming to the “going off the road” issue later in this entry, but the next step was to try and balance their spawning, de-spawning, and the density of the crowd. I firstly needed to make sure an equal number were spawning in front of the player and behind the player, and that some NPCs would spawn directly at the gates, even if those gates are in full sight of the player, and that they would then cut back across the player’s movement. Once that was done, and people were likely to spawn in front of the player, and behind, and at all different locations – and a full complement of civilians was spawned before the player even set foot into a map grid – we had something which looked much better. Here’s a gif of watching a wide range of people wandering around (for now it is spawning them with a random culture, rather than spawning an appropriate population distribution for each nation), and then after they’ve walked around for a bit, I decided to have a closer ‘l’ook at one of them and browse their clothing:


And here’s a comparable screenshot of “examining a passing NPC” in progress, which I have chosen simply because I really liked how this guy looked:


Two stages now remain: to ensure this works for all city districts (and then extend it to tribal settlements, fortresses, towns, etc), and to also make sure that sometimes NPCs wander off the road and go exploring on their own. The first is still in progress, but the second seems to be going reasonably well. The objective is to get the NPCs very rarely “breaking off” from the road and heading to other places on the map, either a randomly-selected location (which they are allowed to walk on), or a door they are allowed to go through (so a random “human” (‘h’) can path towards a random house in a lower-class or middle-class district, and then if the player sees them go through, that NPC is then associated with that house). Equally, we should have a small number of NPCs spawn off roads out of the player’s line of sight, and then path towards the roads, and then move towards road properly. When working nicely, this gets the majority of NPCs keeping to the roads, whilst very rarely we see one of the NPCs break off and head elsewhere, and if you follow them, they will either carve a path through the terrain or make their way to a door and then pass through – I’m clearly going to need some flavour text for “You see a person go through a door”, “You hear a door open and shut” if you’re right next to it but don’t actually see them go through, etc (whilst making sure this doesn’t get obnoxious and it doesn’t fill up the message log). As was suggested in a previous thread, I’m also going to add lots of flavour text when you enter/exit buildings, but that’ll come later this release. I’m still finishing off the pathfinding to non-road areas, so that’ll probably come next week when I’ll likely have finished pathfinding (I hope) and have the remainder of that to show off, and possibly some other clothing too? See you then. In the mean time, you can keep up to date on my devlog, Facebook page, or Twitter!

Post comment Comments  (50 - 60 of 131)
romenigcandido
romenigcandido Jan 2 2013, 1:46pm says:

I must say that I created an account just to be able to follow the development of this game, and if you ever decide to charge for the game I'll be more than happy to pay. The game seems to be extremely complex, which is something that I love, not to mention that you make ASCII graphics into something beautiful to behold. My sincere congratulations!

+5 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Jan 4 2013, 9:44am replied:

My sincere thanks! Very glad you like the concept and the graphics. As I speak, I'm finishing off the religious symbol generation (which there will be a blog entry on next week), which is itself another graphical route I'm exploring (along with flags). Let me know if you have any thoughts/ideas for the game in general, anyway :)

+2 votes   reply to comment
romenigcandido
romenigcandido Jan 4 2013, 11:50am replied:

I have some questions and ideas about Religions, but I'll wait for the next update to comment on the matter.

+2 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Jan 4 2013, 8:08pm replied:

Cool; I await them come Monday :).

+2 votes   reply to comment
Arethrid
Arethrid Jan 1 2013, 2:48pm says:

I am looking forward to see this project's final version :)

+2 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Jan 4 2013, 8:57am replied:

Thanks :) - though I couldn't possibly say when that will be...

+2 votes   reply to comment
taylan!
taylan! Dec 30 2012, 10:34pm says:

Looks like a very ambitious game and highly interesting. I downloaded 0.2.1 and played around a bit. One thing that I noticed was the frequent loading pauses in the game (to load zones, I assume?), which can be bothersome after a while. Oh and the game crashed for some reason. Are you interested in crash logs to be emailed to you?

+2 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Dec 31 2012, 9:56pm replied:

Re: loading, yes, loading does happen often. However, it seems much more often because there is nothing "to do" yet, so to speak - if you're spending half an hour on a single map grid, the odd loading screen shouldn't be a trouble, whereas just running across a map grid is going to trigger another load screen very quickly. Yes, please, absolutely re: the crash log, and info about OS as well :)

+2 votes   reply to comment
HereticUK
HereticUK Dec 10 2012, 6:59am says:

I would like to ask if possible about the language implementation in the game. What are your plans for this? How are you going to do this? As a student of languages it really interests me.

+2 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Dec 10 2012, 8:16am replied:

Thanks for the question! Well, a longer explanation is going to go up on a blog entry in the future, but here's the brief one. The game produces two kinds of languages from scratch, either based around syllables (so it will generate a database of syllables for that language, like 'car' or 'ur' or 'ab' and piece them together into words) or based around chances of letters, so a language might have 'z' as its most common letter and 'h' as second, so it'll have a preference for those, and same goes for vowels. Each produces visually different languages. The ancient languages in the game do not use a Latin alphabet, but I'm not saying any more about those for a while! If an NPC says a word to you in another language, the game first checks if you know it - if so, it is translated - if not, it checks if a non-English word for that English word yet exists in that language's dictionary. If yes, it uses that word (so 'the' will always be translated the same), if no, it creates a word, checks that word is unique, then adds it to the dictionary. I know this means that all languages have the same grammar/syntax/whatever as English, which is far from true, but from a gameplay perspective I felt they had to keep the same structure to help the player make sense of half-translated sentences, and also because a system for the game recognizing adjectives, nouns, verbs etc and re-ordering them would be a) immensely complex, b) unnoticeable to a player looking at a non-translated language, and c) would prevent the player making informed guesses at unknown words. Shout with any more questions :)

+2 votes   reply to comment
HereticUK
HereticUK Dec 12 2012, 7:27am replied:

That is a very interesting way of generating languages... I shall be keeping an eye on this for sure!

So, will the player character have to learn new languages in order to communicate with others?

+2 votes     reply to comment
MichaelSeph
MichaelSeph Dec 3 2012, 5:53pm says:

Oh My Gosh O.o

+3 votes     reply to comment
UltimaRatioRegum Creator
UltimaRatioRegum Dec 4 2012, 7:10pm replied:

I apparently cannot just post :), but please nevertheless accept my appreciation for your comment!

+2 votes   reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
Ultima Ratio Regum
Platform
Windows
Developed By
UltimaRatioRegum
Engine
Custom Built
Contact
Send Message
Official Page
Ultimaratioregum.co.uk
Release Date
TBD
Game Watch
Track this game
Share
Style
Genre
Roguelike
Theme
Realism
Players
Single Player
Project
Indie
Boxshot
Boxshot
Twitter

Latest tweets from

It can take up to a few hours for tweets to begin appearing.

Embed Buttons

Promote Ultima Ratio Regum on your homepage or blog by selecting a button and using the embed code provided (more).

Ultima Ratio Regum
Ultima Ratio Regum
Statistics
Last Update
1 day ago
Watchers
482 members
News
111