A lightweight fill-tool kind of system that updates pathing map

[Zwiebelchen]

We all know this problem: We have areas in our maps that the player isn't supposed to enter. Like that giant lake of doodad-water or that mountain chain. You carefully block any entry into that zone via pathing blockers... so far so good. But now, as we added a jump spell to the mix, suddenly players are able to enter that supposed-to-be-unpathable zone easily...

What are we going to do? Spam hundreds of pathing blockers to lock the zone? Nah. A "fill" type of tool would be handy!


And this is where the lab comes into play!

The basics about how it could work:

• There is a native that allows manually enabling/disabling the pathability of a 16x16 cell. I don't recall the name now, but I have been using it quite a few times already, so it's definitely there
• The user defines a list of X,Y "seed" coordinates that are meant to be unpathable and inside the zone that is meant to be blocked off
• The system takes those coordinates, then expands from those in all directions until it hits a pathing blocker, kind of like "filling" tools in graphical applications like Paint
• To reduce the load, the system will only iterate a defined number of steps per interval, processed in the background while the players are already playing the map
• The system writes the coordinates/cells processed into a table and as soon as the filling process is completed, loops through them to turn the pathing for those cells off

As looping through tiles one by one is very taxing on performance (a 480x480 maximum scale map can have up to 16.7 million pathing cells), we either need to run a continuous interation process in the background while the players are already playing (this requires the mapper to carefully select the "entry points" of this system so that players won't suddenly reach areas that haven't been filled yet), or we have to check for the operation limit and front-load the entire calculation on map init and live with a longer loading screen.


So... any volunteers that want to code this? I think this could be extremely useful for almost any mapper. Let's do this!

http://en.wikipedia.org/wiki/Flood_fill

 

[Xonok]

In this case we should likely think about how to define the area and perhaps how to loop through the cells of a rect.
Or maybe it would be more practical with some kind of a tool integrated into JNGPE. That would provide absolute control over every single tile without impacting the performance of the map at runtime.
However, I'm not sure how deep the editor hacks actually can go.
A third option would be a tool that adds the pathing maps of doodads and destructibles into the actual pathing map. This approach would have the benefit of being able to be used as a post-processing tool, instead of hacking the editor and would once again not have a performance impact in game.

 

[Zwiebelchen]

Post-processing this is already possible.
Just extract the pathing map via an image converter, then use paint to fill the areas and import it back in.

I think a runtime-processor for this would still be interesting, as it allows dynamically filling and releasing areas depending on how the game changes.
Remember that it's possible to add and remove destructables, for example, to block off areas that are initially accessable, but then get inaccessable as they get filled with lava or destroyed by cave-ins.

If someone wants to code a 3rd party tool that does this as a post-processor kind of like vex map optimizer, all power to you (I'd definitely use it!), but it's unlikely someone will invest time and effort into it. The chance is higher to get a run-time solution.

 

[Ceday]

What is the main goal here?Get rid of unneccesary pathing blocker destructables or save mapmaker time or save loading time?If the main problem is first and/or last one, I guess it would be easier to let mapper enter the area as a polygon and let the polygon fill algorithm do the rest.If its the second one, filling with mouse and hand will be easier for sure.

 

[Arhowk]

If someone wants to code a 3rd party tool that does this as a post-processor kind of like vex map optimizer, all power to you (I'd definitely use it!), but it's unlikely someone will invest time and effort into it. The chance is higher to get a run-time solution.

Anyone with the skill to do this knows a postprocessor is much easier and much more efficient, an in-game processor should be nothing more than a temp workaround unless the pathing is dynamic. I've researched the file formats of the wc3 pathing map and its nothing difficult, though certainly time consuming.

Also be wary of your use of the first person plural commands

So... any volunteers that want to code this? I think this could be extremely useful for almost any mapper. Let's do this!

 

[Zwiebelchen]

Anyone with the skill to do this knows a postprocessor is much easier and much more efficient, an in-game processor should be nothing more than a temp workaround unless the pathing is dynamic. I've researched the file formats of the wc3 pathing map and its nothing difficult, though certainly time consuming.

It's not like the actual algorithm is hard to create. In fact, if you read the wiki article you'll notice it's already there in pseudo-code. We just have to translate it into a vJass library... and you must agree that the chances that someone chimes in and makes a library out of this are bigger than that this person spends time and effort in Java or whatever programming language of your choice to code a 3rd party tool.

I might be wrong though.

I'd do it on my own if I had the time. There's a lot of people that code JASS libraries in the jass section just because. We have plenty of resources with almost no practical applications. So here I am, presenting you with an idea that actually HAS a real practical purpose. Dear JASS section, do this before creating another unit indexer or spellcast system.

What is the main goal here?Get rid of unneccesary pathing blocker destructables or save mapmaker time or save loading time?

Getting rid of pathing blockers. Saving time is just a beneficial side-effect.

If the main problem is first and/or last one, I guess it would be easier to let mapper enter the area as a polygon and let the polygon fill algorithm do the rest.If its the second one, filling with mouse and hand will be easier for sure.

How often do you really have polygonal areas that you want to block of? Natural terrain like mountains usually are extremely irregular. Defining polygons would just make it terribly inconvenient for the mapper. Also, the flood-fill algorithm isn't even that much slower than filling polygons if optimized properly.

 

[GhostWolf]

It would actually be pretty easy to write a tool for this, if the pathing file's specs aren't obscure.
You just convert to/from binary monochrome images.

 

[edo494]

its actually harder to write Jass version of this compared to external program, while at the same time, it would be better to have Jass version instead of external program.

I would do it but I have exams until end of january, and there are certain constraits that have to be met(the pre-existing non-changing pathing inside the area you want to change pathing for must be of different type than the one you are laying down)

 

[Zwiebelchen]

its actually harder to write Jass version of this compared to external program, while at the same time, it would be better to have Jass version instead of external program.

Again, a 3rd party tool is welcome! Then again, we basicly have that already with GIMP/Photoshop/Paint.

The problem is: the pathing map is seperate from the editor pathing, afaik. I don't know what will happen if you open the map in the editor with an edited pathing map so it's more or less just a finalizer like map optimizer.

I would do it but I have exams until end of january, and there are certain constraits that have to be met(the pre-existing non-changing pathing inside the area you want to change pathing for must be of different type than the one you are laying down)

Why? The scan-line flood fill algorithm (as shown in the GIF) should work no matter if the pathing for the fill and outlines are different or not. It basicly inverts the pathing for all cells until reaching a cell that already has the inverted pathing.

The only problem would be turning the filled area back to its initial state. But we can always do that by pushing the cells onto a stack when filling them and just loop through the stack when the player wants to reverse pathability again.

 

[edo494]

The ops tho, the ops

 

[GhostWolf]

I don't get why you'd want to do a flood fill for this.
Specifying a polygon made from N vertices and getting all tiles in it is a lot easier and deterministic (or do you want flood fill except oops, the person forgot to close a region and you just filled the whole map).

Checking against a convex polygon is very easy (point in polygon test).
Checking against a concave polygon is usually done by splitting it to convex polygons and checking against them.

 

[Zwiebelchen]

I don't get why you'd want to do a flood fill for this.
Specifying a polygon made from N vertices and getting all tiles in it is a lot easier and deterministic (or do you want flood fill except oops, the person forgot to close a region and you just filled the whole map).

Checking against a convex polygon is very easy (point in polygon test).
Checking against a concave polygon is usually done by splitting it to convex polygons and checking against them.

It's a matter of usability. A polygon approach requires the user to input all corner points. It's just not as useful as a flood-fill algorithm that only needs one point per area defined by the user.

If the area that needs to be filled is complex because of natural looking terrain, the number of corner points increases dramatically.

 

[GhostWolf]

The number of vertices reflects the number of pathing blockers you'd need in the first place (not really though, it will be less, depending on the geometry).

When it comes to a shoot-and-forget flood fill, who said the area you think is closed, is closed?

 

[Zwiebelchen]

The number of vertices reflects the number of pathing blockers you'd need in the first place (not really though, it will be less, depending on the geometry).

But you'd need to input them manually. With pathing blockers you just do what you do: you place them artistically. With a point-based registry, you now manually have to check and type in all the coordinates...

When it comes to a shoot-and-forget flood fill, who said the area you think is closed, is closed?

Nobody. But graphic tools won't care for that either. It's up to the user to go sure the area is closed.

Also, I think this is actually a beneficial side-effect to find out if there are holes in your pathing players could abuse to reach places they shouldn't be able to reach.

 

[BPower]

Very interesting idea. It should be this native

function SetTerrainPathableBJ takes location where, pathingtype t, boolean flag returns nothing
    call SetTerrainPathable(GetLocationX(where), GetLocationY(where), t, flag)
endfunction

 

[WaterKnight]

Pathing cells are 32*32, so ~3,7mio of them on a 480x480 map. I would have the user provide coordinates in the accessable areas. Postprocessing can be mixed with ingame functionality. A lightweight ingame strategy imho would be to check after the unit stops his special movement, whether the landing area exceeds a certain space. If it does not, block it, if it does, mark it as checked, so it does not need to do so next time.

The major difficulty I see in both @compiletime or runtime is that destructables do not count to terrain pathing, so you would have to additionally make efforts in reading the object data and afterwards the pathing maps. Well normally you should not use destructables where they are not meant as destructable. Also if you count destructables and remove them ingame, you would have to check if the area/adjacent areas are still unaccessable but even if you possess the pathing map for each object type, you still do not quite know if the regions are blocked by more destructables. You would either have to pick nearby destructables and check their pathing or you use an integer/list how many/which destructables belong to the single cell.

 

[Zwiebelchen]

The major difficulty I see in both @compiletime or runtime is that destructables do not count to terrain pathing, so you would have to additionally make efforts in reading the object data and afterwards the pathing maps.

This is not a problem really. I wrote a snippet that removes all destructable pathing blockers and uses SetTerrainPathable to block the pathing for those cells to improve performance.

I just never uploaded it here as there was already such a resource (a buggy one though; for some reason, the creator thought that the smallest pathing cell was 64x64, not 32x32).

 

[WaterKnight]

Did you scan it moving an item around the destructable's location? Commited an edit above.

 

[Zwiebelchen]

Did you scan it moving an item around the destructable's location? Commited an edit above.

The snippet only replaces actual destructable "pathing blockers", in other words: only destructables with no model. And you can enumerate destructables.
The shapes of the blockers are hardcoded (1 small, 1 big, 1 vertical, 1 horizontal and 2 diagonal blockers based on fence pathing textures).

This is actually more performant than using Doodads, as doodads remain in the game, while with destructable blockers, I basicly only place them as placeholders before manually setting the pathable flag for that tile and removing the blocker.
It increases loading time of the map by 1-2 seconds due to the front-loading nature of enumerating on map init, though.


But I really think you are over-complicating this.
A scan-line algorithm could just move an invisible item to the center of the checked 32x32 cell. As we only need to know which points are unpathable, not what is the closest possible pathing around, this approach is sufficient. Also, we don't care for units either.

 

[WaterKnight]

But people usually use more than a few hardcoded pathing blockers. Like trees. Doodads would be more effective if you deleted them @compiletime.

One downside of item placement is that items block each other. Rather than enumerating everything and sweeping it out of the way, I would advise to assign items to their current position (since the block position is grid-snapped).

 

[Zwiebelchen]

But people usually use more than a few hardcoded pathing blockers. Like trees. Doodads would be more effective if you deleted them @compiletime.

Then again, we need a 3rd party tool for that. Which we don't have and won't get as almost nobody writes tools anymore. We have bigger chances to make this possible with a runtime JASS system.

One downside of item placement is that items block each other. Rather than enumerating everything and sweeping it out of the way, I would advise to assign items to their current position (since the block position is grid-snapped).

Why should items blocking each other be a problem for this? We don't want to detect the closest possible pathing, we just want to detect non-pathable areas. If an item doesn't appear on the spot we move it at, we know the area is blocked. Even if it was moved due to another item, there is no problem stopping the algorithm there, as it's up to the user to define proper entry points for the algorithm and keeping the borders of the areas clean

 

[WaterKnight]

The user wants to give the entry points by the area that is supposed to be clear. Items moving around should not be a criteria because as you stated initially, it's only about the pathing map. The extreme case would be a whole patch of items slicing the connected regions apart.

I am confident that I can write a simple static fill with terrain pathing. I already have libs for dealing with the formats. Does the New JNGP allow the simple integration of external tools into the compiler chain? Back then I suggested to strongly decouple the development map from the compiled result.

 

[Xonok]

Having worked on changing JNGPE very recently I can say that every part that's mentioned in the JassHelper manual is handled by calling the jasshelper on the map. So there's no way to put some stuff in between without changing the source code. (I hoped I would be able to put things between importing and vJASS construct evaluation, but wasn't able to)

 

[Zwiebelchen]

The user wants to give the entry points by the area that is supposed to be clear. Items moving around should not be a criteria because as you stated initially, it's only about the pathing map. The extreme case would be a whole patch of items slicing the connected regions apart.

I am confident that I can write a simple static fill with terrain pathing. I already have libs for dealing with the formats. Does the New JNGP allow the simple integration of external tools into the compiler chain? Back then I suggested to strongly decouple the development map from the compiled result.

Building this directly into JNGP, eh? Seems difficult, considering how JNGP basicly only injects into the ordinary editor and is not a standalone editor by itself. I doubt Moyack has the power to actually add new "tools" to the editor aside from compiler-related stuff.

But just in case he can: an additional working layer for painting the shadow map manually would be sick aswell. If one is possible, the other should aswell, considering that both just read/write a seperate image file.

 

[edo494]

you can run lua scripts when map is saved, and if you execute your function on the map from the lua script, you can do anything to the map archive before or after JassHelper runs

 

[Zwiebelchen]

you can run lua scripts when map is saved, and if you execute your function on the map from the lua script, you can do anything to the map archive before or after JassHelper runs

I don't think there's any LUA command that allows to write into the pathing map.

 

[Waffle]

@Zwiebelchen

lua is a programming language..

now im not a lua pro (i like wrote less than 100 lines in my life total) but im 99.999% sure it has some facility to read/write files and/or call external code so i really can't believe it would be difficulty by any means .

the only language that i have seen (apart possibly from SQL but im noob at tyhat too so maybe its an undeserved mention..) that cant read files is JASS2 itself .
and even that can read files...

 

[edo494]

wehack.lua is called when you save the map I believe, because you can see the compiler execute code in there, and while you cant manip the contents, you can call program that manips the contents

 

[Xonok]

I don't think there's any LUA command that allows to write into the pathing map.

http://pscript-lang.googlecode.com/...42bc3ad3e/Wurstpack/grimext/GrimexManual.html
Check the "Path Mapper" part. Maybe it's good enough, maybe we'll need a lua script based on it.

wehack.lua is called when you save the map I believe, because you can see the compiler execute code in there, and while you cant manip the contents, you can call program that manips the contents

Adding to that, note that JassHelper appears to be a single block entirely with everything that post-processes the map script. It calls object merger and stuff like that if used in the map script.
I would find it very handy if someone rewrote JassHelper in a more modular way. I personally would benefit most from having a phase where the external scripts have been imported (//! import), but no script changes have been done.

 

[WaterKnight]

Afaik PathMapper only works for tile types.

Externalcalls are possible. What I also did before was to replace the jasshelper.exe. But that is not map-specific. So I guess it would be better to use an externalcall for the triggering at least. I would like to do it as a JNGP tool, you only need to copy the new files into your JNGP directory then and change your jasshelper.conf. JNGP provides a lua5.1.dll, which I have failed to successfully deploy yet. Else I would use it to start a Lua interpreter. The other issue is, as mentioned above, you should not actually transform the map you save in the World Editor because that would twist what the editor perceives as well and be dangerous through recursion. That's why it is better to copy the map, transform the duplicate and provide some mechanism/easy access to run it. Which raises the question, does JNGP also in a way wrap the Play Test button?

edit: Any idea what the pathing types 0x01, 0x10 and 0x80 are? Placing doodads adds 0x80.

edit2: The algorithm itself was easy but I have trouble linking it all together. I do not suppose you want to install my Lua libs.

 

[WaterKnight]

Try the attached tool in combination with http://www.hiveworkshop.com/forums/warcraft-editing-tools-277/jngp-postproc-262192/

Place it in JNPG\exttools\
Then go to JNGP\jasshelper.conf and insert the line

"PathFiller","exttools\\pathFiller\\pathFiller.exe"

in section [externaltools]

The tool only considers the wpm, so no destructables. It's a mess anyway because I have not found out yet how to successfully link everything together. It should also be noted that it currently is cell-exact, so one cell is enough for a pathway. I guess I will later add an option that it requires two cells because units usually only fit through two.

 

[Zwiebelchen]

Cool, I'll test this out this week if I can find the time.