<div dir="ltr">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.<br><br><br></div><br><div class="gmail_quote"><div dir="ltr">On Sun, Oct 14, 2018 at 8:44 AM Ralph Versteegen <<a href="mailto:teeemcee@gmail.com">teeemcee@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr">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.<br><a href="https://bitbucket.org/rbv/ohrrpgce/commits/9fa6e152ed7867178a5d1190a4867ee2ed3b518b" target="_blank">https://bitbucket.org/rbv/ohrrpgce/commits/9fa6e152ed7867178a5d1190a4867ee2ed3b518b</a><br><br></div><div>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<br></div></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, 13 Oct 2018 at 03:04, Ralph Versteegen <<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>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.<br></div><div>Well, I guess I can just insert a call to GetZonesAtTile in AStarPathfinder.cost_before_node and time it...<br></div><div>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.<br>(Also, we could cache the cost for each tile the first time it's visited - it could probably be stored in the npccache)<br>Ideally the cache could be reused between multiple A* calls, but that isn't possible if the costs per zone are changing.)<br><br></div><div>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.<br></div><div><br></div></div><div>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...<br></div><div dir="ltr"><div><br><br><div class="gmail_quote"><div dir="ltr">On Fri, 12 Oct 2018 at 13:26, James Paige <<a href="mailto:Bob@hamsterrepublic.com" target="_blank">Bob@hamsterrepublic.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div>Hmmm... interesting.<br><br></div>I wouldn't want to rule out zones just yet.<br><br></div>What if each zone had an optional "cost" attached to it?<br><br></div>Using zones is a pretty easy way to define costs.<br><br></div>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.<br><br></div>As for multiple different costmaps for scripting, what if there was just a scripting command to change zone "cost"<br><br></div>So suppose I am scripting a tactics games.<br><br></div>- Before pathing a land unit, set default costs for grass, forest, river, mountain<br></div>- Before pathing a forest unit, set low cost for forest, default for others<br></div>- Before pathing a water unit, set low cost for river, higher than default for others<br></div>- Before pathing a mountain unit...etc..<br><br></div>I feel like that would be an easy and intuitive interface for scripters, which would result in effectively unlimited costmaps.<br><br></div>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.<br><br></div>What if there was a list of per-NPC-definition per-zone cost overrides?<br><br></div>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.<br><br>---<br></div>James<br><br><div><div><div><div><div><div><div><div><div><br><br><div><div><div><div><div><div><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Oct 11, 2018 at 7:56 PM Ralph Versteegen <<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>(Long train of thought leading to some conclusions, included only to indicate my reasoning)<br></div><div dir="ltr"><br>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.<br><br>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.<br>We don't necessarily need to support an unlimited number - e.g. 3 would probably be enough for almost anyone.<br><br>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.<br>(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.)<br><br>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.<br><br>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.<br><br>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.<br>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.<br>And if you use a single map layer for costs, that places heavy constraints on how you split your tiles across map layers.<br><br>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?<br>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.<br><br>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".<br>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.<br><br></div></div>
_______________________________________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.org</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org</a><br>
</blockquote></div>
_______________________________________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.org</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org</a><br>
</blockquote></div></div></div></div></div>
</blockquote></div>
_______________________________________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.org</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org</a><br>
</blockquote></div>