Pathfinding IV — Call it a day, period!

The demo video is here:

Added multi-movement types functionality and portal connectivity. The multi-movement types is sort of self-explanatory. For the portal, do the A* as usual, but besides checking all geometrically connected polygons, also need to check the ones connected via portal. And if two polygons are connected via portal, the estimation of their mutual distance is 0. And then a list of polygons are returned from A*, in the case that portals were used in the path, then the list of polygons are not continuous, say, 1,2,3,7,8,9,12,13,14. Meaning 3 has a portal and we arrive at 7 directly, then we move to a portal on 9 and reach 12 directly. So I run funnel algorithm three times over each continuous segment, 1~3, then 4~6 then 12~14, then add their path together.

So by now I think I got a pretty good understanding of A* and navmesh how they work together. Could even do some beyond-basic tricks over it. The project still has lots of room to optimize. During the past three weeks, or maybe four, I lost count, I’ve been working on it from time to time during weekend, and some workday nights. So probably about 30 hours haven been spent, again lost count. I think now it’s a good time to refresh my mind a little bit and unplug from it for a while. For the potential improvements, I might switch back to this project in the future and work on them.

Haven’t determined what’s the next thing I wanna work on, I will use this week to come up with something interesting. Maybe it’s time to learn some WebGL, or maybe dig deeper into Procedural City Generation (I’ve done some work related to it before, when I was a student, in a class project, but since time was limited, I didn’t implement it very well), or maybe try some other game technology. There are so much I need to learn, ah…

Now it’s Monday morning, let wish this upcoming week is a good one! ūüôā

Advertisements

Pathfinding III

It’s easy to get a workin prototype but it’s hard to get all details work perfectly. I worked another two nights on it and currently I’m happy with how it works, fixed lots of bugs. Here is a video showing the pathfinding.

In the video, 7s ~ 18s, there was some unoptimized path chosen. So what happened is:

Image
So basically what I did is, in the A* algorithm, I use polygon center as the node location, so in the above figure, A* chooses B over A. But actually if A is chosen, then path C will be the actual path after funnel algorithm, while D is the one funneled from B. Clearly C is better than D, but in my implementation which uses polygon center as node position, B and D are the result I get. In these URL, the similar problem was mentioned:

http://digestingduck.blogspot.com/2010/05/towards-better-navmesh-path-planning.html

http://digestingduck.blogspot.com/2010/08/navmesh-node-locations.html

And in his post he mentioned a nice paper(http://graphics.ucmerced.edu/projects/10-sca-tripath/) which can solve this problem(or maybe solve it partially). I didn’t go through that paper yet because I currently have higher priority to-do than that optimization. But one day I will see how to improve it.

Actually I didn’t wanna post the progress until I put a character in and implement some other functionalities. But it seems I haven’t posted anything for a week or so, so I wrote this post so that you know I’m still alive hah.

So the plan for tomorrow is to put a character, make him walk instead of only having a sphere rolling. Also I wanna try to give each different polygon different move type. Say some are swim, some are walk, and some vertical ones are climb. Then the character will switch animation based on which polygon he’s on.

Pathfinding II — Funnel Algorithm

Lots of things happened during the past week so I didn’t have time, or maybe to say the initiative, to work on the pathfinding project until yesterday. The A* over navmesh is basically done. I would write a post later today or within several days to show the result and talk about some points that worth attention.

In this post, I will just write down some key points about the [Funnel Algorithm]. I really spent hours to figure it out. During the process, I found this one very helpful:

http://cs.brown.edu/courses/cs195u/lectures/06.pdf

The most valuable parts are these two pages (completely taken from the above lecture note of Brown University)

Image

Image

there are several things that I implemented differently from the above lecture note, the first is I take the character size into consideration. As a result, zero length funnel side is no longer a problem because even two edges share the same end point, after offsetting it with character size, the two positions are different

So here is the pseudo code of funnel algorithm in case I forget how it works in the future, or maybe it can even help someone else implementing it then it would be my pleasure. I did it in a recursive way, there might be more elegant way of doing that. I will think of it.

Image

Image

Basically one should be able to implement the funnel algorithm after reading the Brown University’s lecture note. The important thing to keep in mind is that, we need to keep two variables:

leftFunnelIndex and rightFunnelIndex so that we know at which depth we need to call the Restart function

and also don’t forget to treat the end point as a size 0 polygon and do the same check as we did for other polygons.

I think this post is done here.

Pathfinding I

About June, last year, I worked on a pathfinding project during spare time just for fun. It was to generate grid-based navigation graph for terrain, and then perform A* algorithm over the graph.  I almost lost all of that project. Now I only left with some screen shots of that.

Image

Image

Yeah that’s it. Sort of naive. LOL.

Long time ago, I read a post here http://www.ai-blog.net/archives/000152.html

Since then, I always wanna implement the navmesh pathfinding. I know there is a brilliant tool called recast, and detour library. Sadly I cannot compile it in Unity Mac. Here, http://www.arongranberg.com there is a guy doing all kinds of pathfinding in Unity. And also several guys seem to be working on translate recast and detour into pure C# so Unity users can use them.

What I’m actually trying to say is, there are great tools out there. But since pathfinding is a incredibly important part of game AI, I would rather implement it myself, even though mine might be rough, so that I can fully understand all the basics of those cutting edge techniques.

Currently I don’t have the ambition to do the automatic navmesh generation. So I created a Unity Editor tool to draw navmesh over the terrain. First I would like to show some results. This is the navmesh I drew for a simple scene, and the whole drawing process took 5 mins or so.

Image

Image

I spent like three nights after work to get to this point (currently it can do nothing than drawing the navmesh, the A* part is completely zero). Some parts that worth mention are:

1. Snap to an existing vertex. Sadly I didn’t figure out a way to snap the mouse position in editor mode. So how I did it was to cast a sphere and if any vertex get hit, I draw a handle disc around that vertex to show that vertex is the one that will be snap to.

2. Originally I wanna draw all the graphics using gizmos. But again, I failed to figure out how to draw a selectable and movable gizmos. (Also I need collider for each vertex so I can check collision when trying to snap) For a project I’ve done before, I knew that instead of gizmos, I can use handles, they can be selected and movable. But I don’t like their visual effect at all. So I decided to create real gameobject.

3. Serialize lots of stuff. BTW, this post is of great value. http://forum.unity3d.com/threads/155352-Serialization-Best-Practices-Megapost?p=1064609#post1064609

This project could be extended a lot. First of all the drawing tool is not super user-friendly(I would like to know how to snap mouse position!!!). But I’m not planning to polish it to the best in the near future. Because at least it works fine for myself. And I guess I”m the only one who really use it. So I will probably live with that for a while. I wish I could finish implementing basic A* over the navmesh during this weekend. And then some other interesting stuff I wanna do is to take character size into consideration when doing the pathfinding, like a guy could pass a door but a fatty cannot. And also assign different types of movement for different polygons. Like one area is marked as swimming, then the character will switch to swimming mode when he’s moving inside that polygon.

Last week I read the article written by some guys from University of Washington talking about flow field. That’s awesome. But I didn’t really understand all the details of it. Every time I read those cool articles, I feel like shit because they are way much better.

Be patient! Maybe one day I will be pro like that, LOL, that will be horrible.

All stories start here

This week my dear friend Devin left Miami with his wife-to-be. And he suggested me to start my own blog to document the project I do during spare time. “It will help”, he said. I’ve been thinking to have a blog since long time ago but just never really started.

Now, here I am.

Yesterday I saw a saying somewhere “Two things define you. Your patience when you have nothing. Your attitude when you have everything.” I find this one helpful. Not sure whether I will have everything some day, but I definitely have nothing right now LOL. So just be patient. Oh, also, yesterday it was raining cats and dogs when I left the office. You just cannot imagine how wet I was. I believe there were fish in my shoes. And the worst part which make me pissed off is that, the rain stopped when I got back home. WTF…

Hopefully, I will post the second post soon talking about some work progress of the project I’m working on for fun, which is a Navmesh and A* pathfinding project in Unity3D.

Happy Friday!

BTW, today is the last day of China’s nationwide college entrance examination of 2013. I went through that exam in 2006, 7 years ago!!! How time flies!! shit.. this fact actually scares me. 7 years ago, I joined Shanghai Jiaotong University, Shanghai, and met lots of good friends there. Oh, I’d better start working than falling into memories. Ganbatte!!