abhuva Mind Reader
Posts : 191 Join date : 20110627 Age : 38 Location : Germany
 Subject: TrianglePoint Collision Detection Algorithm Thu Oct 06, 2011 12:52 pm  
 You may wonder what this shall be, so let me introduce first to my basic idea: I wanted to be able to check what region a given party is into (for example if player is in snake land, or ashenborn etc..). Based on this i want to further improve my Unique Battlefields idea (region specific battlefields). Now to implement this i wanted to put hidden partys at the regions border points and check if the player is inside the npoly this forms. The solution is to break this down further and make a check if the player is inside a given triangle. Based on this article: http://www.blackpawn.com/texts/pointinpoly/default.htmli tried my own implementation into the modulesystem. After some problems (ms dont let me use floating point variables) i finally have a working algorithm. Now we could use this for a lot of stuff. Basicly it just checks if a party A is inside the triangle formed from party B,C and D... This can be either towns etc.. but also moving parties like lords. Maybe this is usefull for other stuff too like AIcoding, rumorscoding (rumors based on the land you are in) etc... Currently the code is still in development, but i wanted to share my first working version:  Spoiler:

## Abhuva Point Triangle Collision Detection ## Script params: 1 = Main party which shall be tested ## 24 = partys forming the triangle ## Output reg0 1 means p1 is inside the triangle ## 0 means p1 is outside the triangle ("point_triangle_collision", [ (store_script_param, ":p1", 1), (store_script_param, ":p2", 2), (store_script_param, ":p3", 3), (store_script_param, ":p4", 4), (party_get_position, pos0, ":p2"), (party_get_position, pos1, ":p3"), (position_get_x, ":Ax", pos0), (position_get_y, ":Ay", pos0), (position_get_x, ":Bx", pos1), (position_get_y, ":By", pos1), (party_get_position, pos0, ":p4"), (position_get_x, ":Cx", pos0), (position_get_y, ":Cy", pos0), (party_get_position, pos0, ":p1"), (position_get_x, ":Px", pos0), (position_get_y, ":Py", pos0), (store_div, ":Ax", ":Ax",1000), (store_div, ":Ay", ":Ay",1000), (store_div, ":Bx", ":Bx",1000), (store_div, ":By", ":By",1000), (store_div, ":Cx", ":Cx",1000), (store_div, ":Cy", ":Cy",1000), (store_div, ":Px", ":Px",1000), (store_div, ":Py", ":Py",1000), ## Now we calculate the vectors out of this (store_sub,":V0x",":Cx",":Ax"), ## V0x = Cx  Ax (store_sub,":V0y",":Cy",":Ay"), ## V0y = Cy  Ay (store_sub,":V1x",":Bx",":Ax"), ## V1x = Bx  Ax (store_sub,":V1y",":By",":Ay"), ## V1y = By  Ay (store_sub,":V2x",":Px",":Ax"), ## V2x = Px  Ax (store_sub,":V2y",":Py",":Ay"), ## V2y = Py  Ay ## Now we calculate the 5 different needed dot products out of those vectors (store_mul,":dot00",":V0x",":V0x"), ## dot00 = (V0x * V0x) + (V0y * V0y) (store_mul,":dot",":V0y",":V0y"), (store_add,":dot00",":dot00",":dot"), (store_mul,":dot01",":V0x",":V1x"), ## dot01 = (V0x * V1x) + (V0y * V1y) (store_mul,":dot",":V0y",":V1y"), (store_add,":dot01",":dot01",":dot"), (store_mul,":dot02",":V0x",":V2x"), ## dot02 = (V0x * V2x) + (V0y * V2y) (store_mul,":dot",":V0y",":V2y"), (store_add,":dot02",":dot02",":dot"), (store_mul,":dot11",":V1x",":V1x"), ## dot11 = (V1x * V1x) + (V1y * V1y) (store_mul,":dot",":V1y",":V1y"), (store_add,":dot11",":dot11",":dot"), (store_mul,":dot12",":V1x",":V2x"), ## dot12 = (V1x * V2x) + (V1y * V2y) (store_mul,":dot",":V1y",":V2y"), (store_add,":dot12",":dot12",":dot"), ## Now we calculate the Barycentric Coordinates u,v and invDenom (store_mul,":invDenom",":dot00",":dot11"), ## invDenom = 1 / ((dot00*dot11)(dot01*dot01)) (store_mul,":dot",":dot01",":dot01"), (store_sub,":invDenom",":invDenom",":dot"), (set_fixed_point_multiplier,1000), (try_begin), ## we use this to avoid division by zero (eq, ":invDenom", 0), (assign, reg0, 0), # we failed anyway (else_try), (store_div,":invDenom",1000000000,":invDenom"),
(store_mul,":u",":dot11",":dot02"), ## u = (dot11*dot02  dot01*dot12) * invDenom (store_mul,":dot",":dot01",":dot12"), (store_sub,":u",":u",":dot"), (store_mul,":u",":u",":invDenom"), (store_mul,":v",":dot00",":dot12"), ## v = (dot00*dot12  dot01*dot02) * invDenom (store_mul,":dot",":dot01",":dot02"), (store_sub,":v",":v",":dot"), (store_mul,":v",":v",":invDenom"), ## Now we can check if the point is inside the Triangle ## (u > 0) & (v > 0) & (u+v < 1) ## we cant use floating point, so i multiplied everything with 1000000000 (this is based on tests) (store_add, ":dot",":u",":v"), (try_begin), (gt, ":u", 0), (gt, ":v", 0), (lt, ":dot",1000000000), (assign, reg0, 1), (else_try), (assign, reg0, 0), (try_end), (try_end), ]),
You pass 4 party idÂ´s .. the first is the party which shall get tested. reg0 will be 0 if its failed and 1 if its inside the triangle. Example: (call_script,"script_point_triangle_collision","p_main_party","p_town_7","p_village_30","p_village_31"), (try_begin), (gt, reg0, 0), (display_message, "@Test passed..."), (else_try), (display_message, "@Test failed..."), (try_end),
Last edited by abhuva on Thu Oct 06, 2011 1:29 pm; edited 1 time in total 
