Staredit Network > Forums > SC1 UMS Theory and Ideas > Topic: Nooks and Crannies
Nooks and Crannies
Sep 16 2009, 2:35 am
By: payne
Pages: < 1 2 3
 

Jan 22 2010, 6:31 pm payne Post #41

:payne:

In fact, more clutter it is, less path possibilities there are D:



None.

Jan 23 2010, 9:09 am Wormer Post #42



I believe "path" should be understood in a bit different more general way. I think this is related to the area connectivity. That way if there are no obstacles on the map the whole map is connected with a single "path". If there is one solid obstacle there are two "paths" to go around it. And so on. Probably not exactly as I've described (because then the number of paths seem to depend exponentially on number of obstacles), but something very very close to this.

To check my theory I've made a test map. The map doesn't give Nooks and Crannies error, but instead crashes my SC. If I leave about 3100 Doodads it still crashes, however 1260 Doodads it doesn't crash. If I convert doodads to terrain it still crashes. ^^

I believe the solution to the Nooks and Crannies mystery lies somewhere around these things.



Some.

Jan 24 2010, 11:34 pm payne Post #43

:payne:

Anything new, farty?
:farty:



None.

Apr 6 2010, 8:41 pm Vrael Post #44





Could these nooks and crannies have something to do with it?



None.

Apr 1 2017, 11:34 am Freakling Post #45

*sluuuuuuuuuuuuuuuuuurp!* Melee Map Maker

Sorry for bumping this really old thread, but since it came up as an issue in the feature request list for the editor, I thought I'd share my observations here:

The reason for this error is most definitely that the BW engine does some kind buffering at game start (creating nodes for path finding on a macro scale, or something like that), as has already been specuated here:
Quote from The Starport
[quote=name:JaFF]My friend had this problem. This error occurs when you simply have too many cramped/cluttered places on the map. It is not just one small place that causes it; you just need to break some set of rules or some test SC performs before launching the map. Tux'es pathfinding AI explanation seems to be the most logical one.

This is in line with the following observation:
If somewhere on a map terrain is changed in a "meaningful way" (like changing the outline of unwalkable areas, changing terrain levels or placing certain doodad tiles that influence pathfinding, like bridge or ramp tiles), it can change unit pathing behaviour at any other part of the map. A typical example would be that moving a choke point around will usually result in new mining bugs (i.e. bad worker pathing from/to resources) popping up somewhere on the map. So unit pathing is provably influenced by more than just the terrain in its immediate vicinity, which strongly suggests units follow some kind of precalculated pattern.
Tscmoo has probably a pretty good idea about the exact mechanics behind it.

Post has been edited 1 time(s), last time on Apr 1 2017, 1:09 pm by Freakling.



None.

Apr 5 2017, 12:27 am Suicidal Insanity Post #46

I see you !

FYI: https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack#comment-806548411

(Refresh twice if it doesn't jump to the comment)




Apr 5 2017, 1:19 am Excalibur Post #47

The sword and the faith

I remember reading this eons ago. Any chance they make this 'hack' better or make an actual working system? I doubt it but one can dream.




SEN Global Moderator and Resident Zealot
-------------------------
The sword and the faith.

:ex:
Sector 12
My stream, live PC building and tech discussion.

Apr 5 2017, 7:31 am TF- Post #48

🤙🏾

I've got a lot of experience messing around with this error. Basically Vrael's image above is right, you will see improvements if you stomp nooks like that with large patches of either pathable or unpathable terrain but not a mix of the two, some types of terrain brushes a thin pathable edge automatically which takes a lot of non-ISOM stomping to correct.

Obviously you can only afford to do that in areas outside the visible play area, or where the artificial terrain is not too visible unless the player gets really nosy.

Another thing that unintuitively helps is adding lots of flat pathable terrain around a complex nook'd area, even if there is already a good amount of pathable terrain around it, for some reason this also helps.

Check out Eternal Death to see the kind of extensive surgery you can do to keep a complex map going.





🤙🏾

Apr 6 2017, 10:35 am Freakling Post #49

*sluuuuuuuuuuuuuuuuuurp!* Melee Map Maker

Wow, thanks for that link. I knew that article by Patrick Wyatt, but I never read through the comments. This pretty much confirms that it works like I suspected. Here's the quote for convenience:


Quote from name:Patrick Wyatt
The basics of the set of path-finding algorithms, which were authored by Brian Fitzgerald (who will consequently be able to speak with much more authority on the subject) were:

1. On map-load, split the map cells into regions which were small (say roughly 10x10 32x32 tiles on average), contiguous and didn't contain any major obstacles. Path-finding inside these areas could be done using A* with few occasions for bumping into obstacles.

2. On map-load, create a higher-level map containing region adjacency. Because the regions were irregularly shaped, this higher level map was a graph of nodes rather than a tile-map.

3. For inter-region path-finding use A* on the higher-level map so that it was not necessary to grind through *every* *single* *8x8* tile on the map -- too time-consuming.

4. As units moved, mark their locations on the individual cells they occupied. Traverse around occupied cells, with lots of special case logic for all sorts of edge cases, unit behaviors, and occupancy cases (bad vs. allied units). The special-case logic included a state machine with something on the order of 40 different states, if I recall correctly.

5. Separate pathing behavior for flying units, obviously. I plan another article on another hack used for flying units.
It would be really really helpful to get an editor function that can simulation the map-load calculations of nodes and regions, I guess. It would definitely help a lot in understanding pathfinding irregularities better.

@Excalibur: They are not gonna touch the core of pathfinding, because it is the essential element of gameplay and hence balance to define Brood War. We would probably very lucky already if the most fatal fringe cases (like units-stacked-and-stuck-on terrain bugs, including the infamous "ramp vortex" [I don't really like that term, because it focuses to much on one special case]) will be resolved...



None.

Options
Pages: < 1 2 3
  Back to forum
Please log in to reply to this topic or to report it.
Members in this topic: None.
[08:59 am]
Corbo -- cause we mainly use discord now
[08:14 am]
Generalpie -- Why doesn't the shoutbox get used as much as it used to anyways?
[08:13 am]
Generalpie -- rekt
[07:59 am]
TF- -- 👊
[02:05 am]
KrayZee -- Vrael
Vrael shouted: depends on what we're talking, 2012 dark knight rises obviously Anne Hathaway/selina kyle, but if we're going 90's The Animated Series Talia all the way
I'm talking about the one you're married to, is it Hathaway or Pfeiffer catwoman?
[09:27 pm]
TF- -- xe
[08:09 pm]
Wing Zero -- I miss when it was named the global maths and rektbox
[06:05 pm]
Roy -- :roy:
[05:22 pm]
Vrael -- none of us do
[05:22 pm]
Vrael -- well I guess that's true, I don't spam in the spambox nearly as often anymore
Please log in to shout.


Members Online: Roy, ryleegfigueroa, weberdos, Casadeise90