Updates Updates Updates...

Finally, all the latest update of PathFinder, TDTK and TBTK is now up on AssetStore.

The current iteration of TBTK is still very buggy at the moment so I wouldnt bother too much about it until the next update.

Next would be PathFinder. It's not really a big update, unless you like to use it for a vertical axis. Before this it use to only support xz-plane (horizontal) grid generation. So basically I've added grid-generation for xy-plane (vertical) following some user request. The next thing on the list would be to add serialization to the grid so it no longer need to be generated everytime the scene start. Still not sure how effective that is going to be in reducing load time, or how straight forward it's going to be implementing it. But we'll see when we get there. So the change log of the latest PathFinder is as follow:

PathFinder Version Change – 1.1.2

• Added support for vertical grid (XY-plane)
• Fix the inconsistency in the example scenes.
• Fix bug where Agrid graph doesnt work if erode is set to zero

Finally, TDTK. The latest update fix a bunch of stuff with editors and the more recently added game play mechanic. The most notable addition would be the addition of the modular tile set to the package as well as the example scene. The updated demo is looking awesome after this small addition along with some lighting. I must urge you to check it out, just look at these screen shots!

However please note that the dsitributed package is export via Unity3.5 so it hasn't got the lighting treatment in the demo. Finally, here's the full list of the change/fix in latest update.

TDTK Version Change – 2.2.4
addition/change

• Icon can now be deleted before building to reduce build size (for NGUI only)
• Added modular tile set to the package, applied to the demo scene.
• Input for Ability system has been changed (right/left click has been swapped).
• Added mobile support for abilityManager
• Added mobile support for drag and drop building scheme
• Tower position during drag and drop phase will now 'sticked' to the cursor, as opposed to the last valid position.
• Change how overlay is assigned in the editors.
• Add option for pre-calculated hit result upon shoot, to prevent tower for firing redundant shot
• (configure in GameControl)

bug fix

• fix bug with spawn editor where generate wave in finite mode gives error
• fix bug where ability armor reduction on creep doesn't work
• fix bug where creating a new scene doesn't work with only 1 resource
• get rid of the warning sign in Unity4.0 and up
• fix bug where path-indicator does not point in the right direction in Unity4.0 and up
• fix bug where DamageTable is not taken into account for shield
• fix bug where shield pierce doesn't work

*For TDTK user,  please note that the dsitributed package is export via Unity3.5 so the example scene hasn't got the lighting treatment as shown in the demo. If you wish to have that, please let me know and I'll send you a copy of the package from Unity4.2.

PathFinder v1.1 is Now Live!

I'm pleased to announce that PathFinder has been given a major overhaul and is now live on AssetStore. Following is the update:

• Added a new graph type which is more memory and performance friendly
• Added binary heap based sorting to the search algorithm, make the search faster
• Path-smoothing has been reworked entirely
• Reorganise structure of the code
• All Example scripts has been rewritten
• C# counter part of the source and examples are now included

With the addition of the new graph and binary heap based sorting, it goes without saying that the new code is a lot more faster. Well, just have a look at this video, I think it shows more than I can possibly say.

The scene shown is setup with a square grid with grid size of 0.5 over an area of 100x100. Effectively 40k nodes. The grid is then optimised and clustered into smaller area based node for more efficient search algorithm. In older code, search a path from end to end with such node resolution would take easily take up to 0.1second or longer. With the new code, well as you probably can see, the queue time for the search is hardly noticeable even with a handful of agent call for search every 0.1seconds. This is largely thanks to the new adaptive node that I used. The adaptive node clusters together an area of smaller node into one. This reduce the total node needed across the whole scene. And since the new node cover a bigger area, the search would involve much less node as each adaptive node would cover much more ground than the evenly distributed grid node. The two images below would show the strong contrast between the two node types.

Adaptive Node, it takes much less of them to cover the area

Typical grid node, there's thousands of them to cover the area

Also the path-smoothing has been improved. The old algorithm has a tendency to cut through area which is suppose to be unwalkable. The new algorithm has eliminate this entirely. And it has a build in mean smoothing to make the corner more... smooth.

Having say that, the new PathFinder is by no mean perfect. There are a lot of places which can use more work. You can expect me to keep working on it. And I have to say, at this point, the path smoothing seems to be a lot more taxing on the performance than the search algorithm itself. I totally didn't expect that. I'm guessing the next logical step would be optimising the path smoothing.

Status Update (NSS is awesome edition)

Just Submitted an update for PathFinder v1.0. I have put substantial amount into this update, almost everything has been rework. But I'll talk about it in later post, probably when the update is approved by Unity. But if you have been following the blog, it's basically about a more optimised and efficient graph type, as well as path-smoothing and addition of C# version of the code.

It's a bit worrying to be honest. My submission of last InputTouches update has been pending for more than 2 weeks. It normally take only a day or two, makes me wondering what has gone wrong. It's also frustrating at the same time that there are people who surely could use the update (which I promised) and I can't get it out. If you are wondering what's the InputTouches update is about, it contains some requested minor change by user as well as a whole set of examples in JS.

I'm looking forward to the approval of these two package. Also I have some plan for AssetStore, possibly a shocker, so stay tuned. :)

Apart from these, I've been working on a new but quite interesting free-lance work. It's still in early prototype and the game won't be available anytime soon. Still, it's always exciting to work on new stuff/mechanic that I haven't try before.

Finally, I should explain the title. What the hell is NSS? It's short for New Star Soccer. A ridiculously addicting and fun iOS game. It's rather terrifying, I find myself play it on my phone all the time, whenever I can, even when I can play stuff like guildwars2 and PES on my PC. However I suppose only those who have interest in football could really relate to it. The fact that it's so simple and yet it manage to capture some of the essence a whole a player contribution in a football match thing successfully is really impressive. Well not all of it is brilliant, certain aspect of it is quite arcady and gamey. Still credit where credit's due, it's really good. Consider that fact that it cost only $1 and it's free to try out. But if you plan to try it out, be warned that it's addicting as hell, so try at your own risk.

PathFinder (Onto bigger and better things literally!)

Not sure why, an rather straight-forward attempt to port PathFinder to C# has lead me into a spree of improvement attempt on it. It has invoke the inner beast within me, that crave for challenge and problem solving. It has taken me more than 2 weeks now trying to do it. 

The good thing is, when PathFinder v1.1 hits. It gonna be better than ever. That is if all my theories to optimise and improve the current version works. Well for a start, I've managed to improve the path-smoothing by a great deal. It's basically what that's mentioned here in this post, only better.

Path-Smoothing

From Top down angle

Apart from that, I've added binary heap to the algorithm. Thanks to this well written article here. It's basically a sorting mechanism that eliminates the need to search through the long list of nodes looking for the shortest path. It's suppose to make the algorithm at least 2-3 time faster on a longer route or larger map. Well, it has certain done that. But I'm still not entirely sure how useful it is, for a very good reason.

That reason being I've been tinkered with various ideas to make the path-finding component goes faster. One solution that seems very promising is clustering smaller nodes, which is a square into a bigger rectangular or square. Bigger square cover more area of course so the map ends up with much less nodes, significantly reduce the nodes that need searching. In other words, instead of scanning through the graph at the step of a small node at a time, the algorithm can skip through large area with no obstacle within it. And so, if the number of node need searching is a lot less, I do wonder how useful binary heap will be in this case. After all, it has its own overhead in the sorting mechanism.

Standard grid-based node

Merge nodes within a clear area into a single node

Back to the clustering of smaller node into bigger node, it's a rather simple concept. Just take the two images above as an example, searching for a path in using the smaller, evenly placed node in the first image could easily need hundreds, if not thousands of iteration through each nodes. But in the second image, a path that originally traverse through hundreds of node is simplified down to a relatively very small number of nodes. Obviously, this is just a variant of two tier path-finding. And to an extent, it is just like navigation-mesh solution. It's not something revolutionary. But hey, whatever solution that works best right?

At this stage, it's very much a WIP. For a start, I could use a better clustering algorithm. And it doesnt like my path smoothing algorithm. Still, it's very interesting to see how it goes.

PathFinder WIP & Coming Update

I'm glad to announce that PathFinder is now getting an overhaul. I've been trying to do this since a few weeks back but only manage to find time now one of the project I've been working on it finished.

I understand that some of the user do prefer C# over JS. For that reason, a C# counterpart will be added to the package. The new C# code will coexist with the current JS code so user will be able to choose their code of choice. Both C# and JS will have exact the same function and feature.

Another thing that will be worked on is the thing that has been bugged me for a while, path-smoothing. The path smoothing in the current version is based on a rather simple Line-of-Sight (LOS) scan. Although it manage to make some of the twisty path straight, it doesnt look very natural. And what bug me the most, it tends to ignore any gap on the walkable surface and "fly" over it. I've added a few more procedural ray-casting along the smooth path to prevent this. So the result is shown in the image bellow:

A comparison of the post LOS smoothing algorithm path. Left: PathFinder v1.0. Right: WIP

The LOS smoothing in current version on the left shows some places where the path over cut the corner as highlighted in the red rectangular. The modified LOS smoothing, which result is shown on the right side of the image, show no obvious over-cutting .

On top of that, I've added another layer of mean smoothing to smooth out the path. The result is a much smoother path. One that is more natural and organic compare to the direct result of LOS smoothing. You can see the difference in the image below, on the right. For comparison sake, the original path found with no post-processing is shown on the right.

The comparison of pre-smoothing and post-smoothing path in the upcoming PathFinder.

Of course, there will be other small tweak, optimisation done to the package other than the smoothing algorithm before the update is finally released. I hope it wont be long from now.

PathFinder Update v1.0f (at long last)

It's very strange that I haven't received much feedback about PathFinder. As a path-finding solution I have expect there should be a lot of bug, little tweak that can improve the package. But that hasn't been the case.

Anyway, I have just submitted a new update to AssetStore. Nothing new, just a series of bug fix following recent feedback I got from user. Thanks to AssetStore sales, now it's finally being used by someone who is not me. Anyway, the list of the fixes included in the update are as follow:

• fixed bug where clustering error occur when the are specified doesn't have similar widht and length.
• fixed bug where agent would stop before just before reaching final waypoint. 
• fixed bug where node generation would encounter error when negative start value for x and z is specified for the area.
• example scripts (chase.js, patrol.js and RTSUnit.js) is now compatible for iOS compilation.

To be honest I don't think path-finding solution is no longer as in demand as it used to be now unity has their built-in path-finding solution. I'm sure Unity will keep on improving the built-in path-finding. That makes me wonder how helpful will a 3rd party solution like PathFinder is going to be come Unity4 in the near future. For that reason, I don't think there's a lot sense in putting more effort into improving this package.

Anyway, I hope user who have made the purchase got what they are looking for.


Edit 1Sep: A hot fix(v1.0f2) has been uploaded and now live on AssetStore following a bug report.

PathFinder Version1.0

PathFinder is now it on Unity AssetStore!

 So here's feature in current version:

•  A* Path-finding algorithm
•  GridGraph Generator applicable in just about any terrain
•  Line-Graph Generator based on user hand-place waypoint
•  Configurable parameter to fine-tune the grah
•  Queue based path-finding call so no lag spike

The package is designed to be flexible, robust and easy to use. Feel free to try out the both demo with custom environment and smooth terrain. Also the link to the documentation.

Here's the link to the Unity AssetStore

PathFinder (Update)

It's been a hectic week. Didn't quite manage to focus on the thing I really wanted to do. 

But anyhow I manged to make some break through. I have optimised the my A* algorithm to a very acceptable speed. A rough average estimation shows that at worse case, it's able to search through around 400 nodes at 1ms. A performance I'm quite happy with. Not quite the "blazing speed" compared to the top unity path-finding pacakge out there but it's certainly powerful enough to meet any requirement of real time game without slowing down the game play.

Beside that, I've also managed to get it working with terrain with varied height. As well as implement a faster and more light-weight auto node generatior. So here's a build for showcase purpose, or bragging right. :)

So I've been working on both path-finding and TDTK v1.2 lately since the next addition of TDTK is gonna need path-finding. So next thing to do would be getting this optimized algorithm running within the frame work of TDTK.

PathFinder

Right, following the lost of all RTS-X source code, I'm back to square one with anything everything I ever done with path-finding. Despite the fact that the one I have before was not very robust, or performance friendly, or flexible in different terrain.

Anyhow I have tried my hand at A* path-finding again. I plan to put it in TDTK for open field tower deployment mode. Figure I would need it in rebuilding RTS-X as well. Only this time I'll do it properly and make a complete path-finding project that would be useful in a variety of other future project I might have. Or at least that's the plan...

So this is what I manage so far:

• auto grid-graph generator on the terrain.
• height-consideration for connecting neighbouring node.
• somewhat optimised standard A* path-finding algorithm.
• post searching path-smoothing.

The performance for this one is not perfect but it's a big improvement from my last attempt some months ago. At least it works alright in this simple demo with 5 agents searching simultaneously without noticeable drop in the framerate. As seen in the image below.

Searched path (start from green dots to red dots) for five agents in blue color

.

The path seraching involves node with different height doesn't quite work yet, especially when the path smoothing comes in. But the path smoothing works just fine. So instead of going through all the nodes in a path like being shown in the image above which make the grid-based path very obvious, the agent only need to traverse through minimal number of path. Hence a more natural path. Just like the image below, a big improvement indeed!

Path smoothing which reslut in much fewer node to go through in each path.

So the next plan would be more optimization to cut down the processing time and get the height difference of the grid to work. I might look into navigation mesh implementation. Something that sound brilliant in theory! But to be honest I myself have been struggle to derive it's implementation from all the material I've look into. This will be interesting...