Sign in to follow this  
xucaen

A* algorithm on a top down vertical scrolling shooter?

Recommended Posts

The screen is not moving continuously, but in increments. A* would work. Not sure why you would want A* search in a vertical shooter though.
 

This did make me wonder about the (extremely loosely) related theoretical question: Is A* search still best for n dimensional searches, or are other searches better in other cases?

Share this post


Link to post
Share on other sites

I agree with Nypyren, the world itself isn't changing, just what's in view.  That said, unless you're vertical shooter has a lot of terrain to pathfind around, basic steering is probably better.

 

EDIT: To expand on my first sentence, think of an RTS like starcraft, does the pathfinding change just because the user is scrolling the viewport?  No, pathfinding is essentially unchanged.

Edited by ferrous

Share this post


Link to post
Share on other sites

It might be the case that the world is procedurally generated on demand.

 

In order to use A* you need to have a starting position and a goal position, and A* will give you the path from start -> finish. So if you have those bits of information and simply want to run the A* algorithm every time the exposed part of the world changes, which might be every frame, then that's do-able in general.

 

However, if as-it sounds your player is constrained such that they can only move horizontally, whilst the world moves vertically, then you have a bit of a snag because you are limited to moving in the following effective directions: up, diagonally up & left, and diagonally up & right. If the resulting path from A* contains portions which require travelling in other directions, then your player will be unable to follow the path.

 

It's at this point that I feel you will need to provide a more detailed description of the problem before we can give the right bit of advice. It might be that what you want is something very different, more along the lines of the minimax algorithm, whereby at any point in time you just want to work out which direction (left, right, or neither) is the most ... erm *productive*.

Share this post


Link to post
Share on other sites

However, if as-it sounds your player is constrained such that they can only move horizontally, whilst the world moves vertically, then you have a bit of a snag because you are limited to moving in the following effective directions: up, diagonally up & left, and diagonally up & right. If the resulting path from A* contains portions which require travelling in other directions, then your player will be unable to follow the path.

 

Those are interesting changes to the algorithm, but shouldn't be too hard to make. If the directions you can move are limited, just don't search the invalid directions when determining the possible path. If everything is constantly moving forward, so relative to the map you can move up faster than you can move down, give upward movement a different cost than downward movement. 

Share this post


Link to post
Share on other sites

A* will continue to do exactly what it does.  In the land of computer theory, A* is a shortest path graph traversal algorithm. It works with any problem that can be converted/reduced into a theoretical graph of with vertices and edges. Dijkstra's algorithm (another shortest path algorithm) can be implemented as a special case, and other shortest path algorithms may also be good solutions in different scenarios.

 

For the problem described there may be many other algorithms.

 

Based on the description, I can imagine most of the gradient descent algorithms could be a good fit. They typically require much less space and processing to compute.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this