A*

[Gambet]

Personally I don't really care whether or not anyone does anything around here anymore with respects to it being beneficial to me, but I figure some proper use and documentation of this search algorithm when it comes to GScript would be highly beneficial for playerworlds to implement to create smarter AI.

Perhaps the GDT can get together for something like this? Chances are no one will bother, but the game is already tile-based so it wouldn't be very difficult to create a grid system and work your way from there. I don't believe much of any documentation exists when it comes to search algorithms and things that are AI-based which is probably why just about all servers lack smart AI.

Feel free to discuss, as stated, I wouldn't use it since I don't log on the game anymore, but when it comes to things that can help push the game forward, this is definitely one of them.

[Twinny]

I've done pathfinding on Graal before with my Sterence Project. It's certainly feasible but my effort had perfect pathfinding with a fairly high load. There was a noticeable hiccup on the server when I did longer a->b finds.

It'd be interesting for a team to provide different solutions. The different heuristics that can be used as well as different methods (such as using a* to find the nearest preset node point to get on a prescripted track)

I'd be interested in getting mine working again (I lost it all via raid failure) but I'll yield to hell Raven being the master of A* on graal if he still reads here.

[xXziroXx]

Both HellRaven and Chompy has had a somewhat completed A* system. I was working on one as well, but abandoned it for reasons I can't remember.

[DustyPorViva]

There have been quite a few scripts made a while ago as everyone jumped to be the first to write up a full working [and efficient] A*... but that was back in GS1. Surprised this wasn't revisited, as back then Graal didn't handle arrays very well at all, and the better support for arrays in GS2 would mean much better A*.

Sadly, that's a lot of processing to be done and real-time A* would probably be too much for Graal to handle. It was quickly determined the best route of pathfinding would be setting up nodes at major intersections of obstacles and letting the NPC pathfind that way. This view may have changed, as, like I said, no one has really brought this up since GS2's arrival. Graal could very well handle it... but I dunno about having multiple baddies on screen trying to pathfind to the player whenever they get out of their line of sight.

[salesman]

I made a pretty decent A* system when I was working on my RTS-based server...I guess I could take another look at it and post it in the code gallery when I have the time.

I wasn't able to finish everything I wanted to do with it, but there's a few things in place to help speed up the pathfinding. It really only started to lag whenever I selected 15 + npcs and told them to move at the same time.

[firefighter]

Our server Zenox uses only a simple pathfinding algorithm with weighting because "real" pathfinding algorithms would lagg the npc server down. Also the algorithm is only used in baddies, when they need to find the way (else they use simple onwall2/onwater2 checks) ;-)

[fowlplay4]

Well I'm sure the best route we could take with this is to develop a solid scripted version and have Stefan implement it efficiently into the NPC-Server & Client.

[DustyPorViva]

There is already the findpathinarray function, lol.

[fowlplay4]

Originally Posted by DustyPorViva

There is already the findpathinarray function, lol.

It's quite basic though, and certainly not the advanced solution we want.

[Chompy]

I made a tactics game using A* pathfinding. It works pretty fast as well. I modified the concept though a little, to find paths in heavy terrain easier.

http://forums.graalonline.com/forums...0&postcount=74 - Screenshots
http://forums.graalonline.com/forums...0&postcount=68 - Video

(The video is old though, I've optimized it more by now)

I've been thinking of adding support for Z-valued tiles to allow jumping etc. (Final Fantasy Tactics anyone?)

[Mark Sir Link]

the pathfinding in the video looks a bit awkward (mostly turning twice instead of once to go diagonal)

[LoneAngelIbesu]

Originally Posted by Chompy

I made a tactics game using A* pathfinding. It works pretty fast as well. I modified the concept though a little, to find paths in heavy terrain easier.

http://forums.graalonline.com/forums...0&postcount=74 - Screenshots
http://forums.graalonline.com/forums...0&postcount=68 - Video

(The video is old though, I've optimized it more by now)

I've been thinking of adding support for Z-valued tiles to allow jumping etc. (Final Fantasy Tactics anyone?)

I remember this. It would be a great thing to release for public use.

[Chompy]

Originally Posted by Mark Sir Link

the pathfinding in the video looks a bit awkward (mostly turning twice instead of once to go diagonal)

I added an option (bool) to enable diagonal movement if wanted

[coreys]

You may be able to get this working at short, single level, distances, maybe even with several AI's using it. But you're never gonna get enough speed from GS2 to run it more realistic environment. I mean, unless you wanna restrict your baddies to that.

[Chompy]

Originally Posted by coreys

You may be able to get this working at short, single level, distances, maybe even with several AI's using it. But you're never gonna get enough speed from GS2 to run it more realistic environment. I mean, unless you wanna restrict your baddies to that.

My A* algorithm ran pretty fast for me, but for others, nope. In the end, it depends on your computer specs. GS2 is fast enough, it really depends on your own computer, as the algorithm is done clientside.

[DustyPorViva]

Originally Posted by Chompy

My A* algorithm ran pretty fast for me, but for others, nope. In the end, it depends on your computer specs. GS2 is fast enough, it really depends on your own computer, as the algorithm is done clientside.

I think the point is, is that many low level languages have a hard time handling path-finding, and something interpretive like Graal is going to have an even harder.

[salesman]

This is why you need to utilize every possible method to help speed up the process (predefining impossible locations, overflow queue, binary heap for sorting, etc)

My A* was pretty damn fast as handling several NPCs searching at the same time, but then again my computer is a beast

[LoneAngelIbesu]

Looks like everybody has A*. But nobody's sharing. Hm.

[salesman]

Originally Posted by LoneAngelIbesu

Looks like everybody has A*. But nobody's sharing. Hm.

I would, but after going back and taking a look at it recently, it's not very code-gallery-friendly, and between school and Era, I just don't have the time.

[Chompy]

Originally Posted by salesman

I would, but after going back and taking a look at it recently, it's not very code-gallery-friendly, and between school and Era, I just don't have the time.

Same here, my A* algorithm is not code gallery friendly atm as it was highly integrated with Crystia's main systems, but I'll probably fix it later making it more code gallery friendly. Basicly the A* is also just a part of a bigger system, a tactics engine (:

And, my A* algorithm never lagged/slowed down for me, not even on long distances with a lot of terrain, but as salesman said, I have a beast of a computer as well x)

[coreys]

Originally Posted by DustyPorViva

I think the point is, is that many low level languages have a hard time handling path-finding, and something interpretive like Graal is going to have an even harder.

Depends on your definition of low level lol
Generally, people consider Assembly low level and I don't think anyone is even going to try creating that algorithm in Assembly.

C++ and some of the faster interpretive languages like Lua and Python handle it just perfectly, however.

The issue is using it smartly. Make sure you're only using it when absolutely necessary. For instance, don't recalculate the path unless the destination has changed a certain amount. If the AI reaches the destination, and the target has changed, then recalculate the path.

Perhaps if you incorporate these (among other) methods you could run it with several in a level on average hardware. It's a longshot, though.

[LoneAngelIbesu]

Originally Posted by salesman

I would, but after going back and taking a look at it recently, it's not very code-gallery-friendly, and between school and Era, I just don't have the time.

Originally Posted by Chompy

Same here, my A* algorithm is not code gallery friendly atm as it was highly integrated with Crystia's main systems, but I'll probably fix it later making it more code gallery friendly. Basicly the A* is also just a part of a bigger system, a tactics engine (:

And, my A* algorithm never lagged/slowed down for me, not even on long distances with a lot of terrain, but as salesman said, I have a beast of a computer as well x)

So post it here, guys. Those of us that are interested in it aren't going to be clueless. I'd just rather not reinvent the wheel, if A* algorithms are already out there.

[fowlplay4]

Originally Posted by LoneAngelIbesu

So post it here, guys. Those of us that are interested in it aren't going to be clueless. I'd just rather not reinvent the wheel, if A* algorithms are already out there.

Yeah, I'm interested now too.