• Advertisement
Sign in to follow this  

Unity Hash Distance & Angle To Produce Unique Value

This topic is 1280 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello

 

I have many vertices drawn on my Unity3d C# application window (thousands). I am attempting to come up with a fast way to detect which vertex has been clicked.

 

My idea is to use a sorted list. The list will be ordered by a vector/vertices distance to (0,0,0):

List <KeyValuePair<double, GameObject>> vectorMap = new List <KeyValuePair<double, GameObject>>();

I use a binary search to order, search and add to the list.

 

Add/Insertion Method:

public void recordElementVertices(Element ele) {
	// Element is a Sub-Class of GameObject

	foreach (Vector3d v in ele.WorldVertices) {
		double distFromZero = Vector3d.Distance(Vector3d.zero, v);

		int index = -1;
		if (Algorithms.LowerBounds(vertexDistanceList, distFromZero, out index, DEF_PRECISION) != Algorithms.SearchResult.FOUND_TARGET)
			vertexDistanceList.Insert(index, new KeyValuePair<double, List<GameObject>>(distFromZero, new List<GameObject>()));
		
		vertexDistanceList[index].Value.Add (ele.gameObject);
	}
}

Hit Test (Search) Method:

public List<GameObject> hits(Vector3d mousePos) {

	int 	index 			= -1;
	double 	distFromZero 	= Vector3d.Distance(Vector3d.zero, mousePos);

	// Binary search will search for an exact hit or find the closest vertex to the mouse pos
	if (Algorithms.BinarySearch(vertexDistanceList, distFromZero, out index, DEF_PRECISION) == Algorithms.SearchResult.FAIL || index < 0)
		return null;

	return vertexDistanceList[index].Value; // return all game objects that occupies that vector position
}

This all works nicely and is fast but there is a major flaw. The algorithm doesn't take into account the vertices angle from (0,0,0). So 2 points that are the exact same distance from (0,0,0) but have different angles will be considered the same vertex when they are not.

 

For example; these 2 points lie 5 metres from (0,0,0) but have different angles. My algorithm will consider these 2 points as occupying the same place in space when they are in a completely different position.

23iikxx.jpg

 

 

Do you have any suggestions how I can hash a distance and angle to produce a unique result that describes that point in space? Some simple like doing Distance ^ Angle could produce a unique result but they would also produce huge numbers. A restriction is that my list sorting algorithm requires that two points close to each other should produce a hash that is similar in order to find points close to the mouse position. Hope that makes sense.

 

I've heard about Locatily Sensitve Hashing but it looks like implementing this algorithm would be very tricky.

 

Any advice would be greatly appreciated.

Edited by gretty

Share this post


Link to post
Share on other sites
Advertisement

What about multiplying the distance and the angle, suitably quantized, and handling angle wraparound properly? Should work, I think, and it takes into account the fact that spacing between angles gets larger as distance increases (if you don't want that, take the square root of the distance instead). Otherwise, you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

Share this post


Link to post
Share on other sites


What about multiplying the distance and the angle, suitably quantized, and handling angle wraparound properly?

 

Thanks for your reply. What do you mean by 'suitably quantized, and handling angle wraparound properly'?

 

If I multiply the angle and distance isn't that going to cause the same collisions? Like for a point with distance = 5 and angle = 10 resolves to 50 and a point with distance = 10 and angle = 5 also resolves to 50?

Share this post


Link to post
Share on other sites


you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

 

Wow, never though of that! A list of Vector2 where x = distance and y = angle may just work!! Thanks!

 

I can also do operator comparisions on Vector2's such as 'if v1 < v2' so that works nicely.

Share this post


Link to post
Share on other sites

Ok, after implementing the advice given to use Vector2's as keys I've got one last query/problem:

 

How should I go about handling angle wraparound?

 

For example; given the 2 points (DISTANCE, ANGLE):  A(100, 10) and B(100, 350). These 2 points are close by but will not be considered by operator comparision (<=, <, >=, >) to be close by.

 

Any ideas how I could handle this?

Edited by gretty

Share this post


Link to post
Share on other sites

check if angles are close for both (A%360, B%360) and (A%360, B%360 - 360)?

 

If either are close, then the angle is close.

 

Edit:

for hashing, use your closeness algorithm to find the closest angle to (1, 0 deg), either ?%360, or ?%360 - 360. Always hash that angle, not the one your are directly given in the function? That might just push the problem out to 180 though.

 

Above, A would convert to (100, 10) before hashing. B would convert to (100, -10). A hypothetical (95, 725) would then convert to (95, 5) before hashing.

Edited by BedderDanu

Share this post


Link to post
Share on other sites

 


you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

 

Wow, never though of that! A list of Vector2 where x = distance and y = angle may just work!! Thanks!

 

I can also do operator comparisions on Vector2's such as 'if v1 < v2' so that works nicely.

 

 

What I meant was convert them to (x, y) points using e.g. (distance * cos(angle), distance * sin(angle)).. not as efficient, but perhaps a bit easier to work with than a distance + angle representation.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By 3dmodelerguy
      So I am building a turn based rogue-like (think CDDA). The game is going to have a very large map (up to 1000's x 1000's) however to alleviate most of that I obviously can't render everything so there will just be render a certain radius around the player and just load in and out data as the player moves.
      The next major system I am prototyping is making interactive tiles destructible and pretty much everything will be destructible besides basic landscape (cars, doors, windows, structures, etc. will be destructible)
      While I am only rendering a certain amount of tiles around the player, I want to keep the amount of colliders active at one time to be as small as possible for performance and currently the tilemap tool I use automatically merges colliders together.
      So instead of creating a separate colliders for each of these tiles and having the destructible behavior tied to that object (which my tilemap tool would allow me to do) I was thinking that I would store an array of all the X and Y locations for the interactive tilemap layer and let the tilemap manage the colliders. 
      Then when I hit a collider on the interactive tilemap layer, instead of of getting the behavior for how to deal with the destruction for that tile from that game object, I would pull it from the array I mentioned earlier based on the tile I attempt to interact with which I already have.
      Does this sound like a good approach? Any other recommendations would be welcomed.
    • By NDraskovic
      Hey guys,
      I have a really weird problem. I'm trying to get some data from a REST service. I'm using the following code:
       
      private void GetTheScores() { UnityWebRequest GetCommand = UnityWebRequest.Get(url); UnityWebRequestAsyncOperation operation = GetCommand.SendWebRequest(); if (!operation.webRequest.isNetworkError) { ResultsContainer rez = JsonUtility.FromJson<ResultsContainer>(operation.webRequest.downloadHandler.text); Debug.Log("Text: " + operation.webRequest.downloadHandler.text); } } The problem is that when I'm in Unity's editor, the request doesn't return anything (operation.webRequest.downloadHandler.text is empty, the Debug.Log command just prints "Text: "), but when I enter the debug mode and insert a breakpoint on that line, then it returns the text properly. Does anyone have an idea why is this happening?
      The real problem I'm trying to solve is that when I receive the text, I can't get the data from the JSON. The markup is really simple:
      [{"id":1,"name":"Player1"},{"id":2,"name":"Player2"}] and I have an object that should accept that data:
      [System.Serializable] public class ResultScript { public int id; public string name; } There is also a class that should accept the array of these objects (which the JSON is returning):
      [System.Serializable] public class ResultsContainer { public ResultScript[] results; } But when I run the code (in the debug mode, to get any result) I get an error: ArgumentException: JSON must represent an object type. I've googled it but none of the proposed solutions work for me.
      Also (regardless if I'm in the debug mode or not) when I try to do some string operations like removing or adding characters to the GET result, the functions return an empty string as a result
      Can you help me with any of these problems?
      Thank you
    • By nihitori
      The Emotional Music Vol. I pack focuses on beautiful and esoteric orchestral music, capable of creating truly emotive and intimate moods. It features detailed chamber strings, cello and piano as the main instruments, resulting in a subtle and elegant sound never before heard in video game royalty-free music assets.

      The pack includes 5 original tracks, as well as a total of 47 loops based on these tracks (long loops for simple use and short loops for custom / complex music layering).

      Unity Asset Store link: https://www.assetstore.unity3d.com/en/#!/content/107032
      Unreal Engine Marketplace link: https://www.unrealengine.com/marketplace/emotional-music-vol-i

      A 15 seconds preview of each main track is available on Soundcloud:
       
    • By RoKabium Games
      Another one of our new UI for #screenshotsaturday. This is the inventory screen for showing what animal fossils you have collected so far. #gamedev #indiedev #sama
    • By eldwin11929
      We're looking for programmers for our project.
      Our project is being made in Unity
      Requirements:
      -Skills in Unity
      -C#
      -Javascript
      -Node.js
      We're looking for programmers who can perform a variety of functions on our project.
      Project is a top-down hack-and-slash pvp dungeon-crawler like game. Game is entirely multiplayer based, using randomized dungeons, and a unique combat system with emphasis on gameplay.
      We have a GDD to work off of, and a Lead Programmer you would work under.
      Assignments may include:
      -Creating new scripts of varying degrees specific to the project (mostly server-side, but sometimes client-side)
      -Assembling already created monsters/characters with existing or non-existing code.
      -Creating VFX
      -Assembling already created environment models
      If interested, please contact: eldwin11929@yahoo.com
      This project is unpaid, but with royalties.
       
      ---
      Additional Project Info:
      Summary:
      Bassetune Reapers is a Player-verus-Player, competitive dungeon crawler. This basically takes on aspects of dungeon crawling, but with a more aggressive setting. Players will have the option to play as the "dungeon-crawlers" (called the 'Knights', or "Knight Class", in-game) or as the "dungeon" itself (literally called the 'Bosses', or "Boss Class", in-game). What this means is that players can choose to play as the people invading the dungeon, or as the dungeon-holders themselves.
      Key Features:
      -Intense, fast-paced combat
      -Multiple skills, weapons, and ways to play the game
      -Tons of different Bosses, Minibosses, creatures and traps to utilize throughout the dungeon
      -Multiple unique environments
      -Interesting, detailed lore behind both the game and world
      -Intricate RPG system
      -Ladder and ranking system
      -Lots of customization for both classes s of customization for both classes
  • Advertisement