[Ohrrpgce] Cost maps

Fri Oct 12 07:04:55 PDT 2018

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/20181013/2fbff77d/attachment-0001.html>