Improvement of nature sounds

[SolarStar]

well you can say it is a bug or maybe not. I think this is wrong. Birds should not sing in the middle of the night. Maybe you can hear an owl.

 

I was in South Red Moon during 4:50 (night-time) and i was really irritated from all this bird activity so that I really thought it was early in the day when it was really in the middle of the night - el-game-time. I hear enviro-forest04.ogg or enviro-forest03.ogg not sure. The enviro-forest-night01.ogg would be much more apropriate !!

[Roja]

Is there any programmer besides Torg(who isn't here), who can take a look into this with me? I found out some of the problem but it seems there is another bug-or perhaps limitation- with the sound boundary areas. Example:

<map id="50" name="Idaloran">
<boundary_def location="Forest lower left quadrant">
	<background>Forest03</background>
	<time_of_day_flags>0x007e</time_of_day_flags>	
	<is_default>1</is_default>		
</boundary_def>
<boundary_def location="Forest lower left quadrant">
	<background>Forest Night02</background>
	<time_of_day_flags>0x0f81</time_of_day_flags>
	<is_default>1</is_default>
</boundary_def>	
<boundary_def location="Beach">
	<background>Waves01</background>
	<point1>10,414</point1>
	<point2>80,492</point2>
	<point3>153,492</point3>
	<point4>75,414</point4>
</boundary_def>
<boundary_def location="Beach">
	<background>Waves01</background>
	<point1>80,493</point1>
	<point2>155,546</point2>
	<point3>255,546</point3>
	<point4>179,493</point4>
</boundary_def>
<boundary_def location="Beach">
	<background>Waves01</background>
	<point1>155,547</point1>
	<point2>253,702</point2>
	<point3>332,702</point3>
	<point4>269,547</point4>	
</boundary_def>
<boundary_def location="spooky forest">
	<background>Atmosphere Spooky01</background>
	<point1>420,473</point1>
	<point2>420,613</point2>
	<point3>568,589</point3>
	<point4>570,473</point4>			
</boundary_def>
<boundary_def location="desert">
	<background>Desert01</background>
	<point1>503,268</point1>
	<point2>594,570</point2>
	<point3>746,570</point3>
	<point4>746,291</point4>		
</boundary_def>

 

Edit: better example above posted....In the above example the locations labeled "beach" do not work. The other locations do work. However the "beach" locations should play along with the 2 default forest sounds.

 

If there is a programmer who can help please pm me and we can discuss it further because i'll have to send you my updated files any way.

[Schmurk]

I had a quick look at the code that is handling those regions and I've found that the code is more complex than it should be. The related function is sound_bounds_check() in sound.c and all the other functions that are called from this one.

 

From what I've seen, the function works like this:

• First, it checks if the given point is in the bounding box of the region. However, here it supposes that the first and third points of the region correspond respectively to the bottom left and top right corners of the bounding box. This greatly limits the shape of the regions you can define which is quite bad IMO.
  
• Then, if the point is in the bounding box, it checks if only 2 points have been defined for the region and if it is the case, it doesn't go further because it assumes that the 2 points correspond to the corners of the bounding box (see first point).
  
• If the region is defined by more than 2 points, it then checks the point against the lines of the region to see if it's inside. Here, it does several tests to decide if it's ok or not and it even computes angles between each adjacent lines of the region to see if the point is in these angles.
  

Well, I've checked the coords you've put in your file Roja and it seems to pass the 2 first tests so I suspect there's a bug in the last tests but it's hard to find where exactly.

 

Anyway, IMHO all the tests are not done properly and I would do them this way:

• First, if we want to allow pure rectangles to have fast tests, then it has to be coded explicitly in the data structure and in the XML file.
  
• Second, the bounding box of the region should not be linked to the corners of the region, it's way too restrictive IMO and may be source of bugs.
  
• Third, there are easier ways to test if a point is inside a convex polygon. A simple solution is to give an orientation to the polygon and then compute the Z coordinate of the cross product between the vectors made by each segment and the point. I mean, if a polygon is defined by 3 points A, B, C and we have a point P, then we have to test the sign of the following cross products: AB ^ AP, BC ^ BP, CA ^ CP. There are maybe better solutions out there but this one is at least better and cleaner than the current one. I think we should also allow to handle convex polygons with less or more than 4 points which could add more flexibilty to the definition of these regions.
  

Anyway, I just give my opinion about the code I've seen but I actually don't have time at all to work on it. So if someone else is interested to work on it, then just do it! (I can still give a few tips if needed...)

[bluap]

Unless someone tells me they are working on this already (I presume Schmurk is not) I'll have a look.

I presume substituting the above text into mapsfx_c2.xml should be enough to see the problem; possibly some map coordinates would help too. If you want to send me some files then please do so, you may already have my email address but I can provide it if required.

[bluap]

Roja and I have investigated further the code appears to be doing what it should; so no bugs to fix.

 

From what I can tell, the current algorithms work fine with a few known limitations. There are several other methods available for detecting if a point is within a polygon, some of which I actually understand! If we were to consider rewriting some of this code, we could consider one where a many sided polygon can be used as this would make it much easier to define arbitrary shaped regions.

 

Schmurk, I'm not sure I understand your comments about the bounding box limitations. It looks to me like the maximum rectangle is calculated correctly. Only if all four points lie on the bounding box are the first & third taken as the box definition which sounds correct to me. Apologies if I'm wrong about that.

 

Anyhow. There are a few of changes I'd like to consider.

 

1) When you walk across boundaries, the current sounds fade out and the new ones fade in. If these happen to be the same sound you get an odd effect. This is especially true if you have a default sound as the default sound fades in then immediately fades out. I'd like to add some code to make this a bit smoother so you don't notice boundaries crossing if the sounds are the same.

 

2) To get multiple sounds to play in for the same region, you have to define the region twice. It might be easier to allow multiple sounds to be defined in a single region definition. This would make configuration easier and save some run-time calculations too.

 

3) IMHO, it would be very useful to be able to visualise the sound configuration for each map. May be Radu is considering this for his rewrite of the map editor. However, one simple thing we could have now would be to draw the bounding boxes on top of the tab-map display, along with some extra information about sound names and times etc. This could be done for a debug build or as a special mode enabled with some option or # command.

Edited February 1, 2009 by bluap

[nathanstenzel]

Just a notion, but if you sprinkled some points around to mark areas that have sounds, you could have a variable volume sound that gets noisier as you get closer and quieter as you get further away. From in the center of a collection of points, it would be the loudest. What would be required is to get a rough distance check for the points of the same sound id. This would require more math, but I am sure there are quite a few rough distance determining formulas out there that produce a rough answer. Average the distances together and have volume=1-average_distance*scale. Just an idea that I thought might help with the realism.

 

Something similar could probably be figured out with the polygon test.

[Roja]

nathanstenzel: There's no point in that. The only times where that would be useful are for sounds that are in a single point to begin with, and that already exists.

[Choris]

you could have a variable volume sound that gets noisier as you get closer and quieter as you get further away.

 

Don't teleporter sounds already do this?

[nathanstenzel]

nathanstenzel: There's no point in that. The only times where that would be useful are for sounds that are in a single point to begin with, and that already exists.

Hmmm....you missed my point. I was actually referring to how you could implement variable volume sounds not based on a single point....but a collection of points. If you treated each sound point individually, you would get overwhelmed with echoes. Treating them as a collection and testing for distance from the collection would be more like the polygon method you were talking about but with more flexibility and variable volume.

 

Do the teleporter sounds work based on one point at a time individually or as a collection of teleporter sound points. If you are near two, do you hear both (possibly out of sync) or just one?

 

I hope I am not distracting from the point too much.

[Schmurk]

From what I can tell, the current algorithms work fine with a few known limitations. There are several other methods available for detecting if a point is within a polygon, some of which I actually understand! If we were to consider rewriting some of this code, we could consider one where a many sided polygon can be used as this would make it much easier to define arbitrary shaped regions.

Totally agree with you. However, handling non convex polygon might be harder.

 

Schmurk, I'm not sure I understand your comments about the bounding box limitations. It looks to me like the maximum rectangle is calculated correctly. Only if all four points lie on the bounding box are the first & third taken as the box definition which sounds correct to me. Apologies if I'm wrong about that.

The bounding box is calculated correctly if we consider that the first and third points always correspond to the bottom left and top right corners but if the region is not defined this way, then it becomes wrong. I don't really understand the need for such a limitation so I think it would be nice to compute the bounding box the usual way and store the result in 4 new variables. With this small change, we could already allow every kind of convex shapes...

[Roja]

I don't really understand the need for such a limitation so I think it would be nice to compute the bounding box the usual way and store the result in 4 new variables. With this small change, we could already allow every kind of convex shapes...

 

I hope this means we do NOT have to redo all the sound areas-if so forget it

[Schmurk]

I don't really understand the need for such a limitation so I think it would be nice to compute the bounding box the usual way and store the result in 4 new variables. With this small change, we could already allow every kind of convex shapes...

 

I hope this means we do NOT have to redo all the sound areas-if so forget it

Of course not. What I'm speaking about is completely transparent from the XML point of view...

[bluap]

Totally agree with you. However, handling non convex polygon might be harder.

The simple methods I found work for convex and non-convex polygons. I just don't know how the loading compares or how much you can pre-compute during initialisation.

 

The bounding box is calculated correctly if we consider that the first and third points always correspond to the bottom left and top right corners but if the region is not defined this way, then it becomes wrong....

I've checked the code again and I'm pretty sure it is OK for both convex and non-convex polygons. The work is done in validate_boundary(). The first stage is to find the maximum and minimum x and y which define the minimum rectangle that can enclose the polygon. This bit does not assume anything about which points to use or the order they are defined. Only if the corners of that rectangle match exactly the points of the polygon is the boundary reduced to two points using the first and third points as the bottom left and top right; a valid thing to do as we know its a rectangle.

 

Hopefully I'm not missing something obvious.

Edited February 3, 2009 by bluap

[Schmurk]

Totally agree with you. However, handling non convex polygon might be harder.

The simple methods I found work for convex and non-convex polygons. I just don't know how the loading compares or how much you can pre-compute during initialisation.

Is it the method that computes intersections between the polygon edges and a line? If it's the case, yes it works fine but there are some particular cases to handle which are not that trivial. BTW, if you want to implement such an algorithm, tell me which version you know because I might have a solution to optimize it a bit.

 

The bounding box is calculated correctly if we consider that the first and third points always correspond to the bottom left and top right corners but if the region is not defined this way, then it becomes wrong....

I've checked the code again and I'm pretty sure it is OK for both convex and non-convex polygons. The work is done in validate_boundary(). The first stage is to find the maximum and minimum x and y which define the minimum rectangle that can enclose the polygon. This bit does not assume anything about which points to use or the order they are defined. Only if the corners of that rectangle match exactly the points of the polygon is the boundary reduced to two points using the first and third points as the bottom left and top right; a valid thing to do as we know its a rectangle.

Ok, I don't remember the validate_boundary() function so at least it uses the good point. However, with the current system, you still can't represent such shapes:

[bluap]

Ok, I don't remember the validate_boundary() function so at least it uses the good point. However, with the current system, you still can't represent such shapes:

OK, so drawing the points in that order leads to the point-in-polygon check failing. You can have a boundary of that shape, but you have to defined the points a different order, BADC in your figure. The validate_boundary() function does calculate the correct outer rectangle, and that check passes the test. However, the polygon check fails. That is unfortunate and I see where our difference of opinion is now; we were checking different bits of the code.

 

BTW, my idea for displaying the boundaries on the tab maps is already there if you compile with DEBUG_MAP_SOUND defined! There appears to be a little bug in that code which I have fixed and will commit to CVS when I've studied it a little further.

[trollson]

Simplest point-in-polygon algorithm would be the ray cast one.

 

From the point, "draw" a line in a given direction, and count the number of line-segments of the polygon it crosses. If this is an odd number then the point is within the polygon, otherwise it is outside.

 

This works for convex and non-convex polygons, and does not depend on winding (for a flat plane at least).

 

Determining the bounding box for the polygon gives an easy optimisation. Of course, you also will always use the same direction for the ray from the point, due north (+y) say, which simplifies the tests.

 

For this application, we need not be overly concerned with boundary conditions (eg, the point lies on an edge or vertex).

 

 

Pseudo code for ray cast algorithm (unchecked C-ish):

(code example deleted due to bug)

 

(while waiting for things to build...)

Edited February 9, 2009 by trollson

[bluap]

Simplest point-in-polygon algorithm would be the ray cast one.

...

For this application, we need not be overly concerned with boundary conditions (eg, the point lies on an edge or vertex).

Yes, that was the simple method I was looking at. There are many web pages and implementations on the net; it's probably a standard computer science assignment. A good starting point as always is wikipedia http://en.wikipedia.org/wiki/Point_in_polygon. I think we would be concerned with the boundary cases, as a point well outside the polygon can be mis-classified if it interacts with the corners. I did find a implementation that resolved this but I've mislaid the link for now.

[Schmurk]

I've written such an algorithm during my thesis and yes, you should not forget the intersections with the corners which lead in several particular cases. This is why I said earlier that this algorithm is not so trivial.

An other version of this algorithm is to search for the intersection point that is the closest to the searched point. Then, when you have this point, if you know the orientation of the polygon, you can deduce the position of the point by checking on which side of the crossed segment/corner is the point. This version can be faster if you cross a lot of corners because you'll have to deal with particular cases only once rather than several times with the original version...

[Torg]

Wow... nice work.

 

This boundary handling was intended mostly as an initial hack as I was sure there were better ways to process the boundaries. (I think there are comments in the code as to something like that).

The reason for the initial rectangle check was because Roja said she would only use rects defined by 2 corners in the XML as it was too complex to get 4 sets of coords for each bit.

 

Anyway, I'll be home again in a week or so and should be able to spend some time on the sound code so if no-one else has taken a look at it, I'll try to tidy up some of the other loose ends mentioned in this and other threads.