15 replies to this topic

[Chesko]

In some bizarre circumstance, you may ask yourself, "How can I determine if the player is inside a region that can't easily be described using a trigger volume cube?" In my case, I needed to determine if the player was in a non-cube-like space that spanned across many, many cells; far too big and complex for a trigger box to be a reasonable solution. So what we want to know is if the player is inside a shape, or (more simply) if a point (the player) is inside a space represented as a polygon. This is actually a rather common problem in computer graphics, called the point in polygon problem. There are several methods to solve it, but here is the one I went with. It is from a code example found here, converted from C to Papyrus.

bool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)
Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series of ordered pairs described in the polyX[] and polyY[] arrays.

Spoiler

bool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)

	;-----------\
	;Description \
	;----------------------------------------------------------------
	;Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series
	;of ordered pairs described in the polyX[] and polyY[] arrays.
	;If (x, y) lies exactly on one of the line segments, this functiom may return True or False.
	;From http://alienryderflex.com/polygon/, converted to Papyrus by Chesko
	
	;-------------\
	;Return Values \
	;----------------------------------------------------------------
	;		True				=		 Point is inside polygon
	;		False				 =		Point lies outside polygon OR polygon arrays are of different lengths

	;float[] polyX = array that describes the polygon's x coordinates
	;float[] polyY = array that describes the polygon's y coordinates
	;float x	   = the x coordinate under test
	;float y	   = the y coordinate under test
	
	;Polygon arrays must be the same length
	if polyX.Length != polyY.Length
		return false
	endif
	
	int polySides = polyX.Length
	int i = 0
	int j = polySides - 1
	bool oddNodes = false

	while i < polySides
		if (((polyY[i] < y && polyY[j] >= y) || (polyY[j] < y && polyY[i] >= y)) && (polyX[i] <= x || polyX[j] <= x))
			if (polyX[i] + (y- polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i])) < x
				oddNodes = !oddNodes
			endif
		endif
		j = i
		i += 1
	endWhile
	
	return oddNodes

endFunction

The function returns true if the point given by x, y is inside the polygon described by the arrays. It will return false if the point is not inside, or if the arrays that you provided as parameters are not the same length. Returning false in the latter case was more ideal to me than dumping a ton of (array index out of range) errors in your papyrus log in the off chance that this occurred.

This function may return true or false if the point is directly on top of a vertex or segment. The function values speed over high levels of accuracy.

Example scenario:

• Let's say I want to know if the player is inside a section of river near Riverwood. Here is the section (in red) that we care about.
• We want to describe the area as a polygon by recording the coordinates of the verticies and writing them down. It ends up being a 10-sided polygon.
• Next, we can take those coordinates and plug them into a script, such as this example:

Spoiler

Scriptname _TEST_myPointInPolygonRiverTest extends Quest

Actor property PlayerRef auto

float[] myRiverPolyX
float[] myRiverPolyY

import debug

Event OnInit()
	;Initialize the array
	myRiverPolyX = new float[10]
	myRiverPolyY = new float[10]
	;Populate array values that describe the polygon
	myRiverPolyX[0] = 14889.85
	myRiverPolyX[1] = 13869.10
	myRiverPolyX[2] = 16938.22
	myRiverPolyX[3] = 17743.47
	myRiverPolyX[4] = 16763.15
	myRiverPolyX[5] = 16811.10
	myRiverPolyX[6] = 17797.28
	myRiverPolyX[7] = 17823.37
	myRiverPolyX[8] = 16988.59
	myRiverPolyX[9] = 16098.66
	myRiverPolyY[0] = -46124.05
	myRiverPolyY[1] = -45167.48
	myRiverPolyY[2] = -43011.81
	myRiverPolyY[3] = -43976.84
	myRiverPolyY[4] = -45001.36
	myRiverPolyY[5] = -45582.18
	myRiverPolyY[6] = -45775.87
	myRiverPolyY[7] = -46529.61
	myRiverPolyY[8] = -46465.85
	myRiverPolyY[9] = -45956.11
	
	RegisterForSingleUpdate(1)
endEvent

Event OnUpdate()
	;Is the player inside the 10-sided polygon?
	bool isInRiverPoly = IsPointInPolygon(myRiverPolyX, myRiverPolyY, PlayerRef.GetPositionX(), PlayerRef.GetPositionY())
	
	if isInRiverPoly
		notification("I'm inside the river polygon!")
	else
		notification("I'm not inside the river polygon!")
	endif
	
	RegisterForSingleUpdate(1)
endEvent


bool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)

	;-----------\
	;Description \
	;----------------------------------------------------------------
	;Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series
	;of ordered pairs described in the polyX[] and polyY[] arrays.
	;If (x, y) lies exactly on one of the line segments, this functiom may return True or False.
	;From http://alienryderflex.com/polygon/, converted to Papyrus by Chesko
	
	;-------------\
	;Return Values \
	;----------------------------------------------------------------
	;		True				=		 Point is inside polygon
	;		False				 =		Point lies outside polygon OR polygon arrays are of different lengths

	;float[] polyX = array that describes the polygon's x coordinates
	;float[] polyY = array that describes the polygon's y coordinates
	;float x	   = the x coordinate under test
	;float y	   = the y coordinate under test
	
	;Polygon arrays must be the same length
	if polyX.Length != polyY.Length
		return false
	endif
	
	int polySides = polyX.Length
	int i = 0
	int j = polySides - 1
	bool oddNodes = false

	while i < polySides
		if (((polyY[i] < y && polyY[j] >= y) || (polyY[j] < y && polyY[i] >= y)) && (polyX[i] <= x || polyX[j] <= x))
			if (polyX[i] + (y- polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i])) < x
				oddNodes = !oddNodes
			endif
		endif
		j = i
		i += 1
	endWhile
	
	return oddNodes

endFunction

We then attach this script to a quest that will run our script for us and see what happens. As you can see, when the player is in the river, we register it, and when he's not, we also see the correct result.

Since this area could easily be described as a set of carefully placed trigger boxes, this probably isn't the best example, but if you expand the size of the polygon to encompass a very large space (multiple cells), then you can see how this might become useful. For example, you could create a space that runs the entire length of a river across many cells to determine if the player is standing in it. Or whatever large-scale application you may need something like this for.

This function should accommodate severely concave polygons, but since the polygon is described as a series of ordered pairs, it will not solve for polygons with a hole in them (since there is no way to describe the hole in a polygon described as a series of connected verticies). A possible way to do this is to describe the hole as a second polygon, and do a test for "if inside "hole" polygon, do x, elseif inside "actual" polygon but not "hole", do y".

Also, because of the maximum size restriction of Papyrus arrays, a polygon could have no more than 128 sides.

Enjoy, I hope someone finds this useful.

Edited by Chesko, 07 September 2012 - 10:33 AM.

[Seigneur Voland]

It seems a good idea, probably better than the crappy (and long) "little fish" trick. But how would you get the float values on the fly ?

[Verteiron]

Thanks for this, I was JUST looking into a way to do this very task.

[Chesko]

It seems a good idea, probably better than the crappy (and long) "little fish" trick. But how would you get the float values on the fly ?

Part of the idea is that the polygon's parameters are known ahead of time. It could be possible to get them at runtime IF you knew the exact shape of the polygon, and could determine the coordinates based on some other relative position (probably the player). What circumstance would you need to get it at runtime?

Another idea would be to use a spell that fired invisible rays from a point, recorded where the impacts occurred, and made those positions the vertices of your polygon.

Edited by Chesko, 06 August 2012 - 06:24 AM.

[Seigneur Voland]

Runtime because, even with 128-sided polygons, wouldn't it be a hell of work to cover all waters of the map ?

This method would be efficient also for some MovableStatic like FXCreek ones, because they have both water & non-water parts, in a way that GetDistance() is really not accurate to detect water.

[DocClox]

You could do a version of that with ref-linked x-markers. Pass the first marker to the function and it talks the chain taking co-ords and adding them into the array. You'd need a fixed size array of course, and a limit function.

You could also bind the array to a script on a MiscObject and create a new instance for each polygon you need to solve for and get some true OO in the process. You could even create a special sort of XMarker for the first node in the chain and use that.

[Chesko]

Runtime because, even with 128-sided polygons, wouldn't it be a hell of work to cover all waters of the map ?

This method would be efficient also for some MovableStatic like FXCreek ones, because they have both water & non-water parts, in a way that GetDistance() is really not accurate to detect water.

It depends entirely on your application, but if that's what you want to do, sure. The river was just an example. You can use this anywhere for arbitrarily boxing up any given space. The difficulty of recording vertices is directly related to how many you have and to what level of accuracy you want. If the mesh has a gentle curve that might take 8 line segments to curve naturally with it, but you only require a rough degree of accuracy, you could use a single angle to describe the curve instead.

DocClox's method of getting the position of a set of ordered markers would be a good idea, though I only recommend getting the marker's position once and then reusing the data, since that many Gets that frequently would take an undesirably long time to execute.

Edited by Chesko, 07 August 2012 - 10:17 AM.

[Arthmoor]

Very cool. Would it be possible to pull the coordinate data out of a region record? Or does Papyrus already have functions to determine if the player is within a defined region?

[Chesko]

To my knowledge, no; this was a large reason why I investigated this. I needed to check if the player was in a Dawnguard weather region, and regions aren't exposed to Papyrus. So, I recorded (roughly) the coordinates of the vertices of the regions I cared about as they appeared in the Region Editor (with slight modification to ensure adjacent regions didn't overlap) and plugged them into arrays that this function checks. Works like a charm

[Arthmoor]

Bummer, all I was able to find is a blank entry for IsPlayerInRegion, so there's a function in the code somewhere for this purpose but I guess it would require SKSE to expose it.

Your method works though, and for the purpose you PM'd me about I already have the coordinates I'd need, I'd just need to pull them out of the region data.

[taewon]

I have an idea, this might speed up development time by placing XMarkers (or Activator Triggers with a distinctive primitive color to see in the CK) at each point of the region your outlining, and adding them to a Form List / Array and obtaining the X,Y positions via Log file-output

Of course you wouldn't do this with your original mod, but a dummy test ESP to create the region points etc. This way you can make your array for your mod with the X,Y Values to use this specific function

Edited by taewon, 24 January 2013 - 02:08 PM.

[ElijahHouck]

Bummer, all I was able to find is a blank entry for IsPlayerInRegion, so there's a function in the code somewhere for this purpose but I guess it would require SKSE to expose it.

Your method works though, and for the purpose you PM'd me about I already have the coordinates I'd need, I'd just need to pull them out of the region data.

That's actually an old command left over from FO3's (maybe Oblivion, too) legacy scripting language.

[Chesko]

That's actually an old command left over from FO3's (maybe Oblivion, too) legacy scripting language.

The condition function IsPlayerInRegion works just fine.

[ElijahHouck]

The condition function IsPlayerInRegion works just fine.

Sure, for dialogue and other condition based actions, but I had assumed you thought it was an undocumented Papyrus function or something. Sorry about that!

[Arthmoor]

No, that was me who thought that. The wiki entries for condition functions aren't always clear on what they're there for.

And for the record, that was introduced in GECK. The Oblivion CS had no such nicety.

[B1gBadDaddy]

I'm not necro'ing this thread, it's relevant and invaluable sometimes. I just wanted to say this is superb.