[Ohrrpgce] Cost maps

Thu Oct 18 17:19:05 PDT 2018

I finally got a chance to look at the branch. It looks like a good approach
to me, especially if you can get the good performance by using a passed-in
buffer.

On Sun, Oct 14, 2018 at 8:44 AM Ralph Versteegen <teeemcee at gmail.com> wrote:

> 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
>>>
>> _______________________________________________
> 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/20181018/6878c22e/attachment.html>