Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 24 Apr 2010
Offline Last Active Today, 11:09 AM

#5313531 Generating all possible combinations of route in a graph?

Posted by on 01 October 2016 - 05:35 PM


For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.

I believe that, given a proper heuristic (distance to destination, for instance), A-star is guaranteed to return an optimal result. (See the "Admissibililty" section of the wikipedia article https://en.wikipedia.org/wiki/A*_search_algorithm) I think this is actually the common case for games, so you'll get an optimal result. Have I missed something?





A* is optimal if you fully close the last node to ensure that there are no neighboring paths that would be shorter. The difference is trivial in some cases, so the step is optional depending on what you're doing. There are several other ways to 'relax' A* in order to fit into performance or memory constraints, such as https://en.wikipedia.org/wiki/SMA*


Regarding OP, if he's searching for paths to multiple destinations then Dijkstra could do it. Just keep expanding until you've touched all the goal nodes and you should end up with a sort of 'all destinations' map. Could take up a lot of memory though depending on the problem space. Without knowing what you're actually doing it's hard to say what the best option would be.

#5313529 How to implement a object manager class?

Posted by on 01 October 2016 - 05:14 PM

Two classes that derive from Entity is Sprite, GameObject.


Noooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo oooooooooooooooooooooooooooo.




(KHawk broke my funny joke.)

#5312703 MVC understanding

Posted by on 26 September 2016 - 12:34 PM



When you really get down to it, the amount of weirdness that happens between a photon hitting something and that information finally reaching your awareness is pretty freaky as well. The things we "see" are actually just an upside-down version of our own private ideas that we superimpose onto color and depth information coming from a stream of photons and translated through a lump of fat in a calcium bubble.

#5312035 Why C# all of a sudden?

Posted by on 22 September 2016 - 11:02 PM

- Popularity of unity.
- Tool development at gamedev companies (these are mostly win + c#

Those were the two factors that eventually motivated me to pick up C#. Especially the latter one, since WinAPI is a magnificent pain in the ass and VS has a forms editor built in to it for C#.

#5311707 Need help with Game Maker

Posted by on 20 September 2016 - 06:25 PM

Well, you could use the free version, or you can...






I believe that they prefer each user to have an account, so honestly I'd just go with the free version unless you really need to publish to alternate platforms or something.

#5311705 Why C# all of a sudden?

Posted by on 20 September 2016 - 06:19 PM

C# applications will even outperform C++ aplications 90% of time



#5311703 Two classes relying on each other

Posted by on 20 September 2016 - 06:15 PM

I need the address of the owner so that the owner can delete the bullet from memory - unless there's some other way I could do it?

The shooter does not need to own the bullets once they're fired. You can have an external container that holds bullets and deals with their logic independently.

class ScaryMonster {

  void immaShootDisFoo(SimpleScene& myParentScene) {


class SimpleScene {
  void spawnBullet(location, direction, speed, etc) {
    bullets.emplace_back(bullet constructor arguments);

  void updateBullets() {
    for(auto& bullet : bullets) { bullet.update(); }
    bullets.erase(std::remove_if(bullet.begin(), bullet.end(), [](Bullet& b) { return b.isDead; }) bullet.end());


  ScaryMonster blerg;
  std::vector<Bullet> bullets;
  ShinyHero derp;


#5311701 Inserting element into vector during iteration causes crash

Posted by on 20 September 2016 - 06:04 PM

I thought this sort of thing would be quite common in C++ so am surprised at this behavior!

Documentation of std::vector will point out that element insertion invalidates iterators.


It looks like this vector is a primary owner for these objects. If you can ensure that the vector outlives anything that may refer to its contents then you could just use std::vector<Test1> and then take references to elements or (preferably) simply refer to them directly as needed. If you're thinking about polymorphism then that won't work though.

#5311115 How many RAM on VDS server I need setup, then my fb game will support 1000 on...

Posted by on 16 September 2016 - 01:20 PM

640K of memory should be enough for anybody.


Have you made Pong yet?

#5311113 My Dream World

Posted by on 16 September 2016 - 01:16 PM

Yeah, I had to move some drives around for it. Longcard is long.

#5310011 Platformer style tutorial. How to import files from tiled etc?

Posted by on 08 September 2016 - 02:31 PM

Sounds like you have a list of individual topics to study. This is also one of the disciplines of programming (research). Trying to find the all-in-one guide is going to cause you more problems than it solves (even if you do find a guide claiming to be this thing).


It sounds like your initial research has led you to a list of things to study more deeply, so the next step is to research each of those topics individually. Continue this process recursively until you understand all that you need to do.


As for loading from tiled specifically, there are libraries available for this. A quick google search found me one for snek.



#5309890 Computer understands your text and is able to speak back

Posted by on 07 September 2016 - 07:00 PM

NLP is a very hard and broad field. It has been around for decades and touches on some of the most advanced research in applied computer science. Throwing that away and pretending you can do better than the accumulated expertise of hundreds (if not thousands) of brilliant people, just because you "dreamed the code", is not healthy.


There is no tutor more capable than failure.

#5309639 SFML converting local object coordinates to global coordinates

Posted by on 06 September 2016 - 04:15 AM

If you're going to scale and rotate as well then you'll need to get familiar with transformation matrices. Most of what you'll find on the subject deals with 3D spaces, but the concept is the same either way. The transform is stored as an N+1 (N being dimensions) matrix that holds the information about the position, orientation, and scale of the object. You multiply each vertex by the matrix to place the object in the world space.

This sounds very complicated, and indeed the math takes a little while to learn, but SFML has the sf::Transform class that can help you work with it.

You'll still want to familiarize yourself with what's going on though, as these operations are the very core of what drives modern renderers, and they're also widely used in physics. There are a ton of resources for learning linear algebra around the internet, as well as for transforms in particular. If you have some time on your hands I recommend MFGD:


But you can also find videos from KhanAcademy and various others just by searching "introduction to transform matrices".

#5309577 SFML converting local object coordinates to global coordinates

Posted by on 05 September 2016 - 07:26 PM

Add the position of the origin to the vertex offset. In your example the world space location of V1 is X + V1. sf::Vector<T> has math operators defines, so something like:

auto worldCoordV1 = triangle.position + triangle.vertices[1];

can work just fine.


Note that if you start involving rotation and scaling then you'll need to account for the whole transform instead of only the translation. What you're really doing here is applying the same transform to each vertex. Generally geometry instances are stored as a collection of vertices (the shape) paired with a transform (the position/scale/rotation). You don't need to have a specific vertex to serve as the origin of the model space.

#5309430 How to design my collision code properly?

Posted by on 04 September 2016 - 03:19 PM

__SKYe got it exactly, and this is an excellent example of why to prefer composition over inheritance.


All I'd add is that you'll probably want to also write some inline functions for reverse order tests:


ret_type check_collision(A& a, B& b) { /* code */ }

inline ret_type check_collision(B& b, A& a) { return check_collision(a, b); }


And also look for other places where you can delegate. For example, sphere v sphere can be delegated to sphere v point.


The composition approach also makes it easy to create composites, where you have a collection of collision primitives wrapped in an object that allows them behave as a single collider.