[Ohrrpgce] Cost maps

[Ralph Versteegen]

Here's a zone-based cost implementation in my zone_costs branch on
bitbucket, but no way to set overrides for different NPCs or by script.
https://bitbucket.org/rbv/ohrrpgce/commits/9fa6e152ed7867178a5d1190a4867ee2ed3b518b

Also, I could speed up GetZonesAtTile to not allocate an array, by instead
passing in a temporary buffer. Then it would be nearly as fast as
CheckZoneAtTile

On Sat, 13 Oct 2018 at 03:04, Ralph Versteegen <teeemcee at gmail.com> wrote:

> As I said, querying the zonemap for all the zones on a tile and then
> computing the cost from that is pretty costly - I implemented zonemaps for
> space instead of speed. I guess this is just speculation without actually
> timing it (and speculation about runtime often turns out to be totally
> worng!), but note that GetZonesAtTile has to allocate an array.
> Well, I guess I can just insert a call to GetZonesAtTile in
> AStarPathfinder.cost_before_node and time it...
> Hmm, actually, this isn't as bad as I thought. I guess the other stuff
> pathfinding does (which come to think of it, includes checking NPC movement
> and avoidance zones) is pretty slow too! This only increases runtime by
> about 50%, with an average of a few zones on each tile. That doesn't
> include time to figure out the cost though, which will require also looking
> up the zone costs and NPC overrides. But it seems like the performance
> argument is not strong.
> (Also, we could cache the cost for each tile the first time it's visited -
> it could probably be stored in the npccache)
> Ideally the cache could be reused between multiple A* calls, but that
> isn't possible if the costs per zone are changing.)
>
> NPC overrides may work; seem a bit awkward. If you add more zones which
> specify a cost, you might have to edit several NPCs (say, bird NPCs) to set
> overrides for the new zones. Maybe they should be set in the zone info
> instead of the NPC definition? Putting NPCs into groups, with a different
> set of zone costs applying to each. Say you set the 'pathfinding cost
> group' for each NPC, have the number of groups set in General Map Data, and
> each zone has an array of costs of each group.
>
> So zones could work. Though I'm not convinced that, though they might be
> an easy way to define costs, they're an easy way to deal with costs. If you
> want to know what cost you (or someone else) has set on a certain tile you
> have to inspect all the zones on that tile one by one, and also check
> whether the NPC has any overrides for each of them, and figure out which of
> the zones has priority. All that for one single tile, if you actually
> understand exactly how the whole thing works! Sounds like you would want a
> way to actually preview the computed cost map in the map editor! Ergg...
>
>
> On Fri, 12 Oct 2018 at 13:26, James Paige <Bob at hamsterrepublic.com> wrote:
>
>> Hmmm... interesting.
>>
>> I wouldn't want to rule out zones just yet.
>>
>> What if each zone had an optional "cost" attached to it?
>>
>> Using zones is a pretty easy way to define costs.
>>
>> I could easily see using this as a nice easy way to mark harm tiles as
>> ones that we don't want to path across unless there is no other choice.
>>
>> As for multiple different costmaps for scripting, what if there was just
>> a scripting command to change zone "cost"
>>
>> So suppose I am scripting a tactics games.
>>
>> - Before pathing a land unit, set default costs for grass, forest, river,
>> mountain
>> - Before pathing a forest unit, set low cost for forest, default for
>> others
>> - Before pathing a water unit, set low cost for river, higher than
>> default for others
>> - Before pathing a mountain unit...etc..
>>
>> I feel like that would be an easy and intuitive interface for scripters,
>> which would result in effectively unlimited costmaps.
>>
>> The downside is that method isn't helpful if you want to use regular NPC
>> pathfinding, but you want different NPCs to path with different costs.
>>
>> What if there was a list of per-NPC-definition per-zone cost overrides?
>>
>> That would be a pretty simple and clear interface-- but it might be more
>> work to implement, and I am not sure if there are bad performance
>> consequences that I have not thought of yet.
>>
>> ---
>> James
>>
>>
>>
>>
>>
>> On Thu, Oct 11, 2018 at 7:56 PM Ralph Versteegen <teeemcee at gmail.com>
>> wrote:
>>
>>> (Long train of thought leading to some conclusions, included only to
>>> indicate my reasoning)
>>>
>>> What our A* implementation is missing is some way to customise the cost
>>> of moving to a tile. It's just a matter of deciding how to specify the
>>> costs. Call that a "costmap". I was discussing this with kylekrack, who
>>> wanted to use them.
>>>
>>> I would like to have the ability to have multiple costmaps - that's
>>> quite important for tactical games, and for flying/swimming NPCs or
>>> vehicles.
>>> We don't necessarily need to support an unlimited number - e.g. 3 would
>>> probably be enough for almost anyone.
>>>
>>> If we had multidimensional arrays in HS, clearly we should have a way to
>>> pass a 2D array of costs to a pathfinding function, but that doesn't cover
>>> pathfinding for normal movement by NPCs unless you're going to script it.
>>> (For efficiency it would be best if these were "typed arrays", like FB
>>> arrays, numpy ndarrays or javascript typed arrays - meaning they can only
>>> store numbers, not objects. We would want these anyway, for accessing
>>> tilemaps/passmaps/etc and sprite pixels.)
>>>
>>> An obvious way to specify costs would be zones... but you would need a
>>> different zone for each different cost value, and how do you support
>>> multiple costmaps? Lower zone IDs override higher ones? Plus reading zones
>>> is relatively slow, especially if you need to check every zone on a tile;
>>> it would probably slow down pathing a lot unless caching is used and the
>>> cache isn't recreated every tick.
>>>
>>> Another obvious solution is to use a tilemap. But just using the tile
>>> IDs as costs? Then they aren't tiles; this would be a costmap, basically
>>> the same thing as a foemap, with a different purpose. With its own map
>>> editor mode? You could use the Paint tool to set the same cost on each
>>> tile, but that would be unnecessarily laborious. I can't see the need for a
>>> costmap editor.
>>>
>>> Assigning a cost to each tile in a tileset and using a tilemap to
>>> specify costs is a more obvious and far easier to use solution.
>>> But... which map layer to use? That has to be a setting somewhere. And
>>> how to support multiple cost maps? You could use different map layers, but
>>> that's going to be a problem if you want cavalry units and soldier units
>>> which have different costs for the same terrain, hence they should inspect
>>> the same map layer. Sounds like you'd want multiple cost lookup tables for
>>> the same tileset.
>>> And if you use a single map layer for costs, that places heavy
>>> constraints on how you split your tiles across map layers.
>>>
>>> Maybe this is silly, and there's little desire to have cost maps for
>>> normal NPC or hero movement as they'll only be used for scripted movement?
>>> What are the uses of costmaps for normal NPC/hero pathing movement?
>>> Having the hero avoid walking on grass. Chase NPCs which follow something
>>> other than the shortest path, for a puzzle...  There don't seem to be many.
>>>
>>> Hence we can just add some script commands to read/write costmaps? Just
>>> like reading/writing map layers - multiple costmaps can be treated the same
>>> as multiple map layers. No "create costmap" and "delete costmap" commands,
>>> only maybe "set number of costmaps".
>>> And there's always the option to add an editing mode to the map editor
>>> for costmaps later. Since cost maps and foe maps are practically the same,
>>> they could even be merged.
>>>
>>> _______________________________________________
>>> Ohrrpgce mailing list
>>> ohrrpgce at lists.motherhamster.org
>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>>
>> _______________________________________________
>> Ohrrpgce mailing list
>> ohrrpgce at lists.motherhamster.org
>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20181015/fc91552c/attachment.html>