Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 01 Sep 2011
Offline Last Active Aug 03 2016 05:57 PM

#5161389 Pathfinding for large units

Posted by on 18 June 2014 - 07:10 PM

So if I'm following you correctly, I'd store an extra set of data for each voxel that is basically a measure of how far away it is from the nearest impassable voxel. I suppose if I only search horizontally when computing that number (since my units aren't always going to be cube shaped), the pathfinding can do a simpler vertical search based on the unit's height.

One thing I don't understand is this step: "For each cell with a value >= 1, look at its neighbors. Take the lowest adjacent clearance score, add 1, update that cell". In order for that to work, it seems like you'd have to process things by starting at the voxels marked 0 and moving outwards. In other words, if you had this: 0 1 1 1 1 1 0, moving from left to right, you'd end up with:

0 & 1 -> select 0, store 1 -> 0 1 1 1 1 1 0
1 & 1 -> select 1, store 2 -> 0 1 2 1 1 1 0

2 & 1 -> select 1, store 2 -> 0 1 2 2 1 1 0   <- should have been 3

2 & 1 -> select 1, store 2 -> 0 1 2 2 2 1 0

2 & 0 -> select 0, store 1 -> 0 1 2 2 2 1 0

The only way I can think of to fix that is to do N passes through the entire set of voxel data, which could take a significant amount of time.


Edit: Actually, having re-read your post, that's exactly what your suggesting.  I guess I can give that a try, but it seems like it would take a while to compute that for the several million voxels that get loaded.

#5161199 Pathfinding for large units

Posted by on 17 June 2014 - 07:52 PM

I'm not entirely sure if this is the right section for this, but here's my problem: I have a 3D voxel world, similar to minecraft, and I'm using A* to do pathfinding for the NPCs. Since the world is laid out in a grid of blocks, I use that same grid for the pathfinding nodes. When the AI follows the path, for units wider than a single grid unit, it gets stuck a lot of times.

The first issue it has is when it comes to a ledge that it needs to drop down from, as shown in my crappy drawing:

The AI gets to the node above the ledge, but can't fall down to the next 3 nodes without moving forwards more.

The other issue is things like doorways, where its physically impossible for the unit to go through due to the size. It would need the pathfinder to path around and find another, larger, opening.

I've tried a bit to make the A* pathfinding work for larger units but the code quickly became a mess and each node check started to require checking a good 15 or so surrounding nodes. Is this the right way to go about it or is there a better solution? Keep in mind its a dynamic world, so precomputed solutions won't work.

#5149088 Issue combining matrix components

Posted by on 23 April 2014 - 07:59 PM

Previously I was multiplying 2 matrices together to do my bone transformations, but now I've broken the matrices down into scale, rotation, translation components. My goal is to work with the component parts so I can perform proper lerping and then combine the final result into a matrix to send off to the GPU. I'm having a problem combining things in this form though.

This is what I did previously: C = A * B. Where those are all matrices. That worked fine. Now what I'm doing is:
C.rotation = A.rotation * B.rotation;
C.translation = A.translation + B.translation;
C.scale = A.scale * B.scale;

Rotation is a quaternion, translation and scale are vector3s. When I combine these 3 components of C into a matrix again: Matrix.Scaling(Scale) * Matrix.RotationQuaternion(Rotation) * Matrix.Translation(Translation) the result is wrong, and my model looks like a collapsed blob.

I'm not sure if this matters, but the original info coming from the model file is a matrix, so I have to decompose the matrix into the 3 component parts on load, which I then store and use for these calculations.

Anyone know what I'm doing wrong here?

#5142337 Hitbox setup

Posted by on 26 March 2014 - 10:35 AM

Doing that gives me this:

RuinValor 2014-03-26 12-31-55-61.png

Which I guess looks right, but if I try to calculate the length it just ends up like the image from the previous post. Also it seems like the boxes that are lying flat correspond to the round ball joints from the Maya images.

#5142189 Hitbox setup

Posted by on 25 March 2014 - 08:43 PM

Yea like I said, the artist (riu) noticed that as well and tried adjusting the right arm bones so they were aligned, but it didn't seem to change the orientation of the boxes at all.

#5141864 Hitbox setup

Posted by on 24 March 2014 - 07:33 PM

The lookat vector of the your bone matrix is most likely either the Y or the Z vector and it would be better in this case to use it instead of the difference vector between bone and parent. In other words, the second pass for all bones would be the more accurate way to do it.

I'm still not sure which vector you're referring to exactly, so I tried the Forward/Up/Right vectors from the parent matrix, and also tried a few like this:
var dir = Matrix.LookAtRH(parentMatrix.TranslationVector, boneMatrix.TranslationVector, parentMatrix.Up).Forward;
Result was just weirdly placed bones:

RuinValor 2014-03-24 20-10-34-90.png

The artist took a look at the bones and thought maybe it had something to do with the transforms on the arm bones being world aligned instead of bone aligned(?), but changing them didn't seem to have any effect. I've attached several pictures of the bones as seen in Maya along with the hierarchy. Maybe someone can spot something wrong from there.

Attached Thumbnails

  • 6okdmkZCLrLRc84yjyNZS5R6vIYa2.jpg
  • 6okdn6M3jrYEj9hBxo2LRxsVmb7KO.jpg
  • 6okdvixdnfhXP9nsdbr06i49ltyHN.jpg
  • 6okdwQyDCmwS9zyXSnsz8vtkCG4Li.jpg
  • 6okdrwVOAfj6cHk9fVcxoTPl3rU7K.jpg

#5141127 Hitbox setup

Posted by on 21 March 2014 - 04:13 PM

So I gave that a try, minus the 2nd pass stuff since there is no "LookAtVector" and I don't think I actually want the end bones anyway, since those should be things like the finger tips and the toes. This is what I got:

RuinValor 2014-03-21 18-08-42-37.png

The fingers and legs are perfect. The hips and arms are the main issue now.

#5140702 Inverse Proportion and Zero

Posted by on 20 March 2014 - 10:47 AM

I am sorry if I was unclear; I was trying to get to the point quickly. I am trying to create an user interface where, in order to pick a color, the user must click within the area of a circle.

That sounds like an HSV color picker. Perhaps you can just use the HSV -> RGB conversion equation? http://en.wikipedia.org/wiki/HSL_and_HSV#Converting_to_RGB

Just one more question: Could you point me to a source of information that discusses the formula you posted?

I just came up with it based off your description. X/10 gives you a 0-1 ratio. 1 - ratio inverts it. Multiply by 255 to scale.

#5140694 Inverse Proportion and Zero

Posted by on 20 March 2014 - 10:09 AM

I don't understand what the radius has to do with it, but if you just want a length of 0 = 255 and length of 10 = 0, all you need is (1 - length / 10) * 255

#5139617 Hitbox setup

Posted by on 16 March 2014 - 10:00 PM

Still a rather odd result from that:

RuinValor 2014-03-16 23-59-52-82.png

#5139614 Hitbox setup

Posted by on 16 March 2014 - 09:50 PM

Hmm, that's a bit odd to use the dir vector there. The 2nd parameter is supposed to be the target position. Anyway here's what that looks like:

RuinValor 2014-03-16 23-46-19-82.png

Negating the dir doesn't change much.

#5139605 Hitbox setup

Posted by on 16 March 2014 - 09:22 PM

The Box function is defined as: Box(Vector3 position, float width, float height, float length)

I did try creating a look-at matrix before, but it didn't turn out well. Mainly the leg bones end up really out of place:

RuinValor 2014-03-16 23-16-33-92.png

And the code for that was just:

var lookAt = Matrix.LookAtRH(center, parentMatrix.TranslationVector, boneMatrix.Up);
var temp = Matrix3X3.CreateFromMatrix(lookAt);

#5139533 Hitbox setup

Posted by on 16 March 2014 - 01:53 PM

Here's the code

private static void BoneDraw(Model model)
	const float width = 1f;
	var bones = model.Bones;

	foreach(var bone in bones)
		var parent = bone.Parent;

		if(parent != null)
			var boneMatrix = model.FinalBoneMatrices[bone.Number];
			var parentMatrix = model.FinalBoneMatrices[parent.Number];
			var length = Vector3.Distance(parentMatrix.TranslationVector, boneMatrix.TranslationVector);
			var dir = Vector3.Normalize(parentMatrix.TranslationVector - boneMatrix.TranslationVector);
			var center = boneMatrix.TranslationVector + dir * length / 2;
			var box = new Box(center, length, width, width);
			var temp = Matrix3X3.CreateFromMatrix(boneMatrix);

			box.OrientationMatrix = temp;

			boneBoxDictionary[bone.Number] = box;

#5139057 Hitbox setup

Posted by on 14 March 2014 - 01:48 PM

Doing that, I'd still end up with the same orientation I'm using now, which seems to be the main issue. I can post the code if it'll help but there's not much to it.

#5138804 Hitbox setup

Posted by on 13 March 2014 - 08:02 PM

I'm trying to build hitboxes around the bones of a model. I took the absolute matrix for each bone and used that to position and orient the boxes. Then I took used the distance between the current bone and its parent as the box length. The result I got was this mess:

RuinValor 2014-03-13 18-42-11-46.png

Also I tried shifting the center to be at the point between the bone and its parent:

RuinValor 2014-03-13 19-15-20-71.png

Which is a bit better but they're still not quite connecting up. Anyone have some advice on how to do this?